Současnému paláci předcházela raně středověká zástavba asi románského dvorcového typu na nároží dálkových cest, dochovaná v partii sklepů. Zřejmě v souvislosti s výstavbou nového mostu byla upravena uliční čára a vznikl gotický dům nejspíše z doby po roce 1342, rovněž zachovaný především v části sklepů a přízemí dnešního uličního křídla. Dům byl dle písemných pramenů upravován ve 2. polovině 16. století a výrazně přestavěn v pozdně renesančním slohu mezi lety 1610 až 1619. V jeho držení je uváděn i Jáchym Ondřej Šlik, který byl za účast ve stavovském povstání v letech 1618 - 1620 popraven, a od r. 1622 patřil konfiskát saským knížatům. V noci z 8. 11. na 9. 11. 1620 se v domě, který předcházel dnešnímu paláci, konalo poslední zasedání královské rady českého "zimního" krále Fridricha Falckého, když utíkal z Prahy po porážce českých stavů v bitvě na Bílé hoře. číst dále

Na počátku 18. století se dům nacházel v majetku hraběte Bredy. Ten zřejmě inicioval první fázi vrcholně barokní přestavby, patrně podle projektu architekta G. B. Alliprandiho, avšak teprve až Jindřich Pavel hrabě Mansfeld, kníže Fondi, který koupil palác v roce 1735, nechal dle písemných zpráv architekta F. I. Préea stavbu dokončit – možná zde působil i B. Scotti. Tehdy již dle popisů existoval palác v základě v dnešním rozsahu, a to i velký oválný sál v zadním křídle, kde však většina dekorací vznikla až v souvislosti s nástropní freskou s námětem shromáždění olympských bohů, kterou provedl v letech 1736-7 Pietro Scotti (figuralista) ve spolupráci s Giovannim Battistou Zaistem (malíř iluzívních architektur) jako apotheosu vítězství Karla VI. a habsburské monarchie nad Turky. S dědičkou Marií Isabellou se roku 1771 oženil František de Paula Gundakar I. kníže Colloredo a dle smlouvy potvrzené Marií Terezií z roku 1775 začal rod pro nejstaršího syna užívat titul říšský hrabě Colloredo- Mannsfeld, později Colloredo-Mansfeld. Palác byl tehdy významným střediskem společenského života rokokové a klasicistní Prahy a počátkem 19. století sem byla převezena colloredovská rodinná sbírka obrazů, založená v Döblingu u Vídně. Již v roce 1808 byla sbírka zpřístupněna veřejnosti a malíř František Horčička nechal v paláci, kde zůstala sbírka do roku 1852, zřídit ateliér pro kopisty. Dokonce v roce 1840 tu otevřela Krasoumná jednota pro Čechy první ze svých pravidelných výročních výstav (je příznačné, že v paláci na počátku 20. století bydlel po nějaký čas během svých pražských studií známý historik dějin umění Antonín Matějček).
V roce 1842 byl k objektu přičleněn a stavebně s ním sjednocen dům, sousedící z jihu (dnes opět oddělený), a už roku 1839 vznikl nový průjezd v pravé části hlavního průčelí, související s úpravou nábřežní komunikace. Po roce 1848 nová majitelka Vilemína provdaná Auersperková podnikla úpravu průčelí a přestavbu zejména interiérů ve stylu druhého rokoka (datace 1853), snad v návaznosti na starší rokokové interiéry. Přestavba v roce 1900 pak radikálně přeřešila vnitřní strukturu západního křídla nad bývalými konírnami. V paláci byla až do roku 1914 v provozu stavovská šermírna, jejíž počátek spadá do roku 1659. Spisovatel A. Jirásek nechal z oken tohoto domu přihlížet F. L. Věka ve stejnojmenném románu korunovačnímu průvodu císaře Leopolda II. (1790 - 1792) v roce 1791. Pozdější úpravy ve 20. století se odehrávaly zejména v partii výkladců a prodejny v přízemí u hlavního průčelí, palác sloužil částečně pro bytové účely a částečně byl využíván jako kanceláře a také knihovna jednoho z pracovišť Akademie věd, později zde působila Lyra Pragensis a pořádaly se zde další kulturní akce. Přesto je architektura i výzdoba paláce pozoruhodně dobře zachovalá a dovolí v budoucnosti obnovit cenné interiéry i exteriéry této významné památky.
Palác uzavřené dispozice svírá svými čtyřmi křídly obdélný dvůr. Hlavní průčelí do Karlovy ulice je dvoupatrové nad nízkým mezipatrem a výrazným prvkem je monumentální vrcholně barokní edikulový portál s pilastry nakoso, zdobený na římse vázami, putti a erbem Colloredo - Mansfeldů (patrně dílo Antonína Brauna), ve střeše pak velké vikýře. Zajímavým prvkem dvorní fasády jsou dvě arkády ve vstupním křídle a protilehlá sala terrena s představenou kašnou s pískovcovou sochou Neptuna s trojzubcem asi z období kolem roku 1735, rovněž kladená do braunovského okruhu. Barokní prostory zejména I. patra, přístupné monumentálním pilířovým schodištěm s kuželkovými balustrádami, mají bohatou rokokovou a druhorokokovou výzdobu stropů, stěn, podlah i dveří (štuky, výmalba, umělé mramory, zrcadla, krby a kamna, parkety, tapety a dřevěná obložení s okenicemi).

Palác měl od roku 1994 v pronájmu nadační fond Polyhymnia. Zavázal se, že památku do deseti let opraví. Nájemce bohužel nedostál svým závazkům, proto město před osmi lety smlouvu rozvázalo a následně vyhlásilo soutěž. Vybrat nového nájemce se ale nepodařilo. Budova ve vlastnictví hlavního města Prahy byla od té doby až do roku 2010 ve správě odboru správy majetku MHMP. V roce 2010 pražští radní převedli Colloredo-Mansfeldský palác do správy Galerie hlavního města Prahy. V budoucnu by v něm mohla vzniknout galerie moderního českého umění, ve které by se vystavovala díla doposud skrytá v depozitáři. Objekt, který čeká na komplexní rekonstrukci, v současnosti zčásti využívá soukromé muzeum umění Artbanka: Museum of Young Art.