21 kwietnia 2004 w Pałacu Prezydenckim, Prezydent Rzeczypospolitej Polskiej Aleksander Kwaśniewski, na podstawie artykułu 161 Konstytucji RP, na wniosek Prezesa Rady Ministrów, odwołał Józefa Oleksego ze składu Rady Ministrów, z urzędów: Wiceprezesa Rady Ministrów oraz Ministra Spraw Wewnętrznych i Administracji. W uroczystości udział wzięli m.in. Leszek Miller, Prezes Rady Ministrów, Jolanta Danielak, Wicemarszałek Senatu, Jerzy Hausner, Wiceprezes Rady Ministrów, Minister Gospodarki, Pracy i Polityki Społecznej, Krzysztof Janik, przewodniczący Klubu Parlamentarnego SLD, członkowie Rady Ministrów oraz ministrowie w Kancelarii Prezydenta RP. Po wręczeniu aktu odwołania prezydent Aleksander Kwaśniewski zwracając się do uczestników uroczystości powiedział m.in. Chcę przede wszystkim podziękować Panu Józefowi Oleksemu, za ten czas, w którym wypełniał obowiązki ministra spraw wewnętrznych i administracji, a także wiceprezesa Rady Ministrów. Zajmował się także problematyką europejską, w ważnym i niełatwym momencie naszej historii. Wiem, że dokładał wszelkich starań, aby w Polsce było bezpiecznie, żeby obywatele mieli takie poczucie, żeby służby, które mu podlegają działały zgodnie z prawem, skutecznie efektywnie. Za to wszystko jak i również za troskę o jakość naszej administracji chciałbym serdecznie podziękować. Józef Oleksy w tym czasie kontynuował swoją pracę na rzecz przygotowania Polski do akcesji z UE. Ten dzień jest dosłownie za chwilę – pierwszego maja będziemy świętować wejście Polski do Unii i Pan Józef Oleksy ma w tym swój osobisty udział. Za to też chcę serdecznie podziękować w przekonaniu, że będzie tę pracę kontynuował. Liczę, że nie będzie szczędził swoich starań, aby Polska nie tylko jak najlepiej weszła do UE, ale żeby spełniło się motto spotkań, które odbywają się w Pałacu Prezydenckim „Silna Polska w silnej Europie”. To jest zadanie dla nas wszystkich tu obecnych, dla naszych Rodaków i również dla Pana Oleksego w nowej roli. Wczoraj w nocy miałem okazję telefonicznie pogratulować wyboru na Marszałka Sejmu. Wybory trudne, wybory jednym głosem mają to do siebie, że wróżą udaną pracę. Wszystko, co rodzi się w bólach zazwyczaj przynosi lepsze owoce, bo docenia się to osiągnięcie, docenia się ten wybór i wierzę, że tak właśnie będzie. Józef Oleksy jako Marszałek Sejmu jest człowiekiem, który ma ogromne doświadczenie, bo funkcję tę już pełnił. Jest osobą otwartą, człowiekiem dialogu, otwartym wobec innych i wierzę, że taki duch będzie panować w polskim parlamencie w najbliższych tygodniach i miesiącach, bo jest to nam bardzo potrzebne. Polska znalazła się w niełatwym momencie zmiany rządu, akcesji do UE, trudności na arenie międzynarodowej, które przecież nie my powodujemy, ale one również nas dotyczą - konieczności skutecznej walki z terroryzmem, zapewnienia bezpieczeństwa naszym rodakom i tym tu w Polsce i naszym wszystkim oficerom, którzy wypełniają misję zagranicą - to są nadzwyczaj skomplikowane zadania, które wymagają współdziałania różnych sił politycznych, osób o różnych poglądach jak i również dobrej współpracy Sejmu z rządem i z prezydentem. Wierzę, że Józef Oleksy, Marszałek Sejmu jest właściwą osobą na właściwym miejscu i że właśnie swoimi cechami charakteru, swoją otwartością pomoże nam w duchu dialogu, duchu sporu, kiedy jest on konieczny, ale także porozumienia, które jest niezbędne dla rozstrzygnięcia spraw tak kształtować działalność Sejmu i współpracę Sejmu z innymi organami państwa. Chciałbym również prosić Józefa Oleksego, Marszałka Sejmu, żeby przywrócił wiarę i zaufanie Polaków do tej jakże zasadniczej instytucji demokracji. Parlament musi się kojarzyć z miejscem, gdzie jest debata, są różne racje, gdzie nawet są konflikty, ale gdzie również są wysokie standardy debaty. Gdzie oponenci szanują się nawzajem i gdzie chodzi przede wszystkim o interes państwa i o racje, a nie wyłącznie o własne emocje czy ambicje. To jest bardzo trudne zadanie, ponieważ wiele w ostatnich latach stało się złego, że ten wizerunek jest taki, a nie inny. Panie Marszałku, chcę życzyć Panu, aby udało się krokami konsekwentnymi, wytrwałością Pana i Pana współpracowników, wszystkich parlamentarzystów RP zbudować taki właśnie obraz Sejmu RP, jednego z fundamentu demokracji, aby była to Izba do której mamy zaufanie.