Na ploše zahrady v její dolní části byly archeologicky zjištěny terény ze 13. století, částečně výrobní, částečně komunikační, přičemž výrobní jsou patrně starší. Po části dnešní zahrady vedla ve středověku komunikace směrem k hlavní, to jest jižní bráně Pražského hradu v prodloužení ulice U Zlaté studně. Její pozůstatky však likvidovala výstavba teras barokní zahrady. Další významná komunikace procházela vedlejším domem čp. 163–III, který za nenápadným zevnějškem skrývá intaktně zachované věžové jádro středověkého domu, na Malé Straně unikátní.

Na parcele paláce byly ve 14. století nejméně dva domy. Oba vyhořely při velkém požáru Malé Strany a Hradčan roku 1541 a byly postupně renesančně znovuvystavěny. Oba zakoupil v roce 1665 Jan Václav Novohradský z Kolowrat, byly jím sjednoceny a výrazně zvelebeny do roku 1669. Roku 1697 koupili výstavný objekt Trauttmannsdofové (Marie Charlotta a Leopold Antonín), kteří jej vlastnili do roku 1727.

S Trauttmannsdorfy se spojuje budování zahrady, existovala však téměř jistě již za Kolowratů. Její osnova je dosud raně barokní ze 17. století, lze ji časově klást mezi dokončení podstatných úprav objektu (1669) a prodej Trauttmannsdorfům, tedy do rozmezí 70.–80. let 17. stol. Buď ještě za Kolowratů nebo až za Trauttmannsdorfů vzniká první sala terrena v patře severního křídla paláce, jejíž stropy zdobí typická velkotvará štukatura pozdního 17. stol. Nejpozději v  19. století zaniklo její otevření do zahrady.

Mladší je druhá (stávající) sala terrena v prodloužení západního křídla. Vznikla ve 20. letech 18. stol. Dříve navrhované autorství Giovanniho Battisty Alliprandiho nebo Františka Maxmiliána Kaňky (oba pro Trauttmannsdorfy pracovali, především v Litomyšli) není příliš pravděpodobné. Některé tvaroslovné prvky stavby, zejména nemotivované křivkové zvlnění středního dílu, ovšem vykazují nápadnou podobnost s koncepcí fasády staroměstského kostela sv. Havla, kde pracoval Kaňkův učitel Pavel Ignác Bayer (zemřel ve vysokém věku až 1733). Pramenné doklady ke stavbě saly terreny však chybí.

V roce 1783 palác získal Josef Krakovský z Kolowrat, který 1801 přikoupil nejzápadnější část (s druhým průjezdem) a celek sjednotil roku 1802 podle plánů Ignáce Jana Nepomuka Palliardiho. Palác tak získal dnešní vzhled včetně průčelí.

1852 palác získávají Ledebourové, následně prováděny především vnitřní úpravy včetně zadní budovy. Nejpozději tehdy (1863) zaniká propojení starší sala terreny se zahradou, nahrazené prostými obdélnými okny.

Po roce 1945 palác patřil ke komplexu budov ministerstva informací, které bylo iniciátorem prvního – neúspěšného – otevření zahrad pro veřejnost.

Roku 1995 byla na parcele objevena románská zeď včetně portálu – jde o Píseckou bránu. Objev doložil, že Malá Strana byla opevněna již v době románské, nejpozději v polovině 12. století. Podoba „brány“ velmi připomíná románské portály Černé věže na Pražském hradě. Románská hradební zeď tvoří východní hranici parcely, zástavba, která již patřila městu, vznikala na západ od ní. Teprve v 15. století jsou zde doloženy objekty, stejně jako sousední rovněž zničené velkým požárem Malé Strany a Hradčan v roce 1541.

V roce 1709 získal stávající dva domy na parcele Jan Josef z Valdštejna. V roce 1712 byl jeho „pražský dům“ jako panský vyjmut z městské jurisdikce. V letech 1715–1720 proběhla hlavní přestavba, kterou řídil valdštejnský architekt František Maxmilián Kaňka, jenž pro Valdštejna pracoval také na Duchcově. Kaňka využil existující konstrukce k vytvoření velkorysé lichoběžníkové palácové dispozice. Jeho autorství nebylo dlouho v odborné literatuře rozpoznáno i vzhledem k relativně prosté podobě vnějších fasád, dnes je nejen uznáváno, ale i doloženo. Vnější neokázalost fasád se ukazuje přímo jako požadavek vkusu stavebníka, hraběte Valdštejna. Jak je u podobných prací F. M. Kaňky obvyklé, palác měl především náročně řešené interiéry a přepychové vnitřní zařízení, za něž hrabě vydával nemalé sumy. Interiéry prodělaly ovšem podstatné zásahy v 19. století. Zároveň s budováním paláce byla řešena i zahrada (tak tomu bylo i na Duchcově), a autorský podíl Kaňkův je tak nepochybný.

Následující majitelé Fürstenbergové palác opravovali až kolem roku 1808/10–1823. Tehdy je zmíněna také „oprava“ zahrad, zřejmě nová úprava parteru včetně vysázení stromů. V roce 1856 byly zbourány domy čp. 156–7–III, čímž vznikla dnešní proluka mezi Pálffyovským a Kolowratským palácem, následně byla řešena obnažená východní stěna budovy. Roku 1881 koupil palác Eduard Pálffy, upravoval jej však pouze utilitárně a roku 1902 jej odprodal státu. Po roce 1950 byl součástí komplexu budov ministerstva informací.

(někdy rozdělována na Kolowratskou při čp. 154–III a Malou Fürstenberskou při tzv. Malém Fürstenberském domě čp. 155–III, ale tyto části tvořily celek náležející k paláci čp. 154–III; navíc při tomto označování může dojít k záměně s Fürstenberskou zahradou při Fürstenberském paláci čp. 153–III)

Pozemky vně malostranské hradby nebyly patrně až do 16. století zastavěny objekty k trvalému obývání, první zmínky o takových objektech jsou až z konce 16. století. Roku 1601 získal městiště Vilém z Lobkowitz, který zde stavěl – avšak v rámci pobělohorské konfiskace jeho majetku bylo místo nárokováno abatyší kláštera sv. Jiří na Pražském hradě, která mimo jiné vznesla stížnost, že na pozemcích patřících klášteru nebyl Lobkowitz oprávněn postavit kamennou stavbu k trvalému obývání, kromě toho pochopitelně žádala vyrovnání za ušlý nájem. Tyto problémy se nadále vlekly, k částečnému vyrovnání došlo až za Götzů v roce 1661. V roce 1621 bylo místo ještě charakterizováno jako odlehlé, přestože naproti se již intensivně připravovala výstavba Valdštejnského paláce čp. 17–III. Hlavní problém však spočíval v tom, že parcela ležela na dvou jurisdikcích – podle údajů část levá a střední patřila městu (městské pozemky před hradbami), pravý, tedy nejvýchodnější díl pak svatojiřskému klášteru, který tu měl pozemky využívané hospodářsky (pravděpodobně vinice, ale nevíme, zda v celém rozsahu těchto pozemků). Neobvyklá majetkoprávní situace se odráží i v atypické dispozici palácových křídel situovaných šikmo k uliční čáře, která rovněž není pravidelná. Jádrem je patrně ještě rovněž nepravidelně disponovaný renesanční objekt Viléma z Lobkowitz. Přes úpravy v 17. století zůstával palácový dům v jádru renesanční, a tak byl koupen Marií Barborou Černínovou z Chudenic roku 1759 za dosti nízkou cenu.

Za této nové majitelky došlo ke zvýšení a zásadní přestavbě, která dala paláci dnešní vzhled, nevíme však přesně, v které době. Hraběnka totiž teprve později zakoupila objekty v zadní části za parcelou, dnešní čp. 155–III, jeden výstavný renesanční dům 1769 a druhý menší až 1776, oba stavebně sjednotila, což vysvětluje naprosto neobvyklou dispozici dnešního objektu, a propojila chodbou s hlavním palácem. Teprve v této etapě se patrně na konečném vzhledu stavby uplatnil architekt Ignác Jan Nepomuk Palliardi. Čp. 155–III sloužilo jako letní palazetto při zahradě, čemuž odpovídalo i jeho vybavení včetně lázně. Přiléhající zahrada tedy dostala dnešní mimořádnou podobu patrně v časovém rozmezí mezi lety 1776 a 1789 (smrt hraběnky). Tvarosloví architektonické složky, která je zde nebývale bohatě zastoupena, svědčí pro autorství Ignáce Jana Nepomuka Palliardiho.

V 19. století se oba objekty opět majetkově oddělily, hlavní palác získali roku 1886 Kolowraté Krakovští a čp. 155–III Fürstenbergové v roce 1868, kteří v této době bourali zástavbu mezi tímto objektem a Pálffyovským palácem, jenž byl toho času rovněž jejich majetkem. Kolowratský palác patřil státu od roku 1918, čp. 155–III bylo vyvlastněno až roku 1945, obě budovy opět propojeny a staly se hlavním sídlem ministerstva informací, následně kultury, které, jak již zmíněno, bylo iniciátorem prvního – neúspěšného – otevření zahrad pro veřejnost.