Den store vinkelformede gulstensbygning på hjørnet af Tøjhusgade og Frederiksholms Kanal blev bygget i 1703-05 til at rumme den kongelige staldetat, som var datidens trafikministerium.
Staldmesteren forestod alle den kongelige hofholdnings transportopgaver og var ansvarlig for det store hestehold, kareter og vogne i den kongelige stald ved Københavns Slot.
Det er uvist, hvem der var bygningens arkitekt. Overbygningsdirektør Wilhelm Friedrich von Platen nævnes ofte. Nyere forskning viser dog, at han ikke selv tegnede, men var en yderst kompetent leder af byggesagerne. Mest sandsynligt var det den polsk-hollandske arkitekt Christof Marselis, som var tilknyttet den kongelige bygningsadministration fra omkring 1702 til 1716 i von Platens embedsperiode.
Bygningen er i to etager over en kælder og med et smukt valmtag i røde teglsten. Hovedporten er i den korte fløj langs kanalen, og den er udformet i kalksten fra Stevns i barokkens romerskprægede formsprog, som også præger hele bygningen.
Staldmestergården er domicil for Børne- og Undervisningsministeriet.