Kazimierz Ujazdowski został jednym z wiceprezesów tej partii (odpowiedzialnym za sprawy zagraniczne). Był współautorem programu tego ugrupowania w dziedzinie kultury, polityki historycznej i zagranicznej oraz partyjnego projektu Konstytucji RP. Od 2 lipca 2004 do końca IV kadencji sprawował funkcję wicemarszałka Sejmu IV kadencji.
W 2005 uzyskał poselską reelekcję, po czym od 31 października 2005 do 7 września 2007 oraz od 12 września 2007 do 16 listopada 2007 ponownie był ministrem kultury i dziedzictwa narodowego. Prowadził wówczas m.in. zakończoną sukcesem międzynarodową kampanię na rzecz zmiany nazwy terenów byłych obozów Auschwitz-Birkenau we wpisie na Liście Światowego Dziedzictwa UNESCO. Był pomysłodawcą Muzeum Historii Polski w Warszawie powołanego 2 maja 2006. 11 marca 2007 utworzył we Wrocławiu Ośrodek „Pamięć i Przyszłość” – instytucję zajmującą się upowszechnianiem dorobku historycznego i kulturowego stworzonego przez mieszkańców ziem przyłączonych do Polski po II wojnie światowej.