Středověké základy paláce jsou hluboce zapuštěny v čase. Na místě dnešní stavby stávaly dva renesanční domy, které byly zase postaveny na gotických obvodových zdích. Při stavebních úpravách sklepů zde objevili základy staveb ze 13. až 14. století, svědectví o starobylosti místa.

Historie paláce je však do značné míry vázána na osudný požár. Dne 2. června 1541 vypukl zničující ohňostroj v domě zvaném „Na baště", který stál na místě dnešního průčelí. Oheň zničil dvě třetiny domů Malé Strany, zasáhl severní část Pražského hradu a poškodit se nepošetřil ani chrám sv. Víta. Parcela pod ruinami domu Na baště se stala na dlouhou dobu neprodejná, город ji považoval za prokletí. Druhý z budov původně patřil císařskému poručíkovi Antoniu Vittalimu, který na dům vyvěsil obraz Panny Marie – tento motiv se zde v různých podobách dochoval až do současnosti.

Teprve v roce 1664 parcelu získal císařský komoří Oldřich Adolf Vratislav ze Šternberka (1627–1703). Zhruba o dvacet let později jeho nástupce koupil i sousední Vittaliho dům. K propojení obou budov v jedinou architekturu došlo v letech 1703–1719 za vlastnictví Františka Damiana ze Šternberka (1667–1723). Předpokládá se, že stavbu vedl podle svého projektu Giovanni Battista Alliprandi. Vnitřní výzdobu paláce pak provedli vyhledávaní štukatéři Giuseppe Donato Frisoni a Giovanni Bartolomeo Cometa, jakož i malíři Jan Rudolf Bys a bratři Abraham a Isaac Godynové. Fasáda si dodnes zachovává barokní obraz Korunování Panny Marie obklopeného svatými patróny objednavatele. Šternberský rodový erb zdobený Řádem zlatého rouna s korunkou připomíná její majitele.

Palác však není významný jen svou architekturou, nýbrž rolí v dějinách české kultury a vědy. V 18. a 19. století se stal vyhledávaným střediskem intelektuálního života. Za panování sběratele umění Františka Josefa hraběte ze Šternberka-Manderscheidu (1763–1830) byla v paláci v roce 1770 založena Soukromá společnost nauk, která byla po dvaceti letech přejmenována na Královskou českou společnost nauk. Zde měla své první sídlo obrazárna, která se posléze stala Národní galerií. V roce 1796 také vznikla Společnost vlasteneckých přátel umění.

U dalšího člena rodu, přírodovědce Kašpara Maria ze Šternberka, se pak scházely vůdčí osobnosti národního obrození – mezi nimi František Palacký, Josef Dobrovský, František Martin Pelcl a Viktor Barvitius. V tomto kruhu byla vypěstována myšlenka zřízení Národního muzea roku 1818 a Společnosti vlasteneckého muzea v Čechách v roce 1820. Šternberský palác tak znamenal rozhodující krok v úsilí o zmapování a uchování české kulturní identity.

Dnes tvoří budova přirozenou součást historického centra Malé Strany a součastně prostorů Poslanecké sněmovny.