Rekonstrukce začala na podzim roku 2002. Brzy se ale objevily problémy se statikou. „Statické problémy způsobené nevhodnými zásahy ve 20. století si vyžádaly nutnost nových technologických postupů a stavebních konstrukcí,“ uvedl tiskový tajemník Kanceláře Senátu Petr Kostka.
Za dalším zdražením byly podle Kostky požadavky památkářů. Ti prosazovali často renovace místo prosté výměny poškozených prvků a žádali i návrat k řešení, která vyplývala z historie, například k původnímu osazení oken a členění okenic.
Většinu z peněz, o které se stavba podražila, získal Senát tím, že omezil jiné investiční akce na léta 2005 - 2007. „O chybějící část prostředků, přibližně třicet milionů, byl v roce 2006 navýšen státní rozpočet v kapitole Senát. Třináct milionů z toho nebylo vyčerpáno a bude vráceno zpět do státního rozpočtu,“ vysvětlil Kostka.
Rekonstrukce Senátu a Kolovratského paláce byla v minulosti mnohokrát kritizována. Jednalo se zejména o stavbu podzemních garáží, jejichž cena se vyšplhala z 20 na 40 milionů korun. To vedlo k odvolání kancléře Senátu Pavla Pelanta v roce 2005.
O jeho osobu se zajímala i policie v souvislosti kvůli výběrovému řízení na rekonstrukci barokního podloubí Salla Terena za devět milionů korun. Stíhání ale zastavila.
