Herzog sprach einen Monat nach Amtsantritt als Bundespräsident auf der Gedenkfeier zum 50. Jahrestag des Warschauer Aufstands. Der Europäer Herzog förderte mit seiner Autorität die Osterweiterung.
Im Mai 1994 wurde Roman Herzog, zu diesem Zeitpunkt Präsident des Bundesverfassungsgerichts, zum Bundespräsidenten gewählt, und sogleich stand ihm eine „heikle Premiere“ (SZ) bevor: Polens Präsident Lech Walesa hatte den Bundespräsidenten zu den Feierlichkeiten zum 50. Jahrestag des Beginns des Warschauer Aufstands gegen die deutsche Besatzungsmacht eingeladen. Die Einladung war in Polen umstritten, einzelne Veteranenverbände und Rechtsparteien hatten gegen die Teilnahme des
deutschen Staatsoberhauptes protestiert.
Herzog reagierte mit Zurückhaltung, betonte aber gegenüber den Medien immer wieder, daß es jetzt darauf ankomme, Gräben zuzuschütten. Sein russischer Kollege Boris Jelzin hingegen, dessen Einladung wegen der Rolle der Sowjets im Warschauer Aufstand ebenfalls in die Kritik geraten war, hatte die Einladung ausgeschlagen. Herzog äußerte in seiner Rede Verständnis für die Widerstände gegen seine Einladung. Er erinnerte an das polnische Leiden und die deutsche Schuld. Auch versicherte er die Anwesenden der Unterstützung Deutschlands für den Beitritt Polens in NATO und EU. Er schloß: „Heute aber verneige ich mich vor den Kämpfern des Warschauer Aufstandes wie vor allen polnischen Opfern des Krieges: Ich bitte um Vergebung für das, was ihnen von Deutschen angetan worden ist.“ In der polnischen und der internationalen Presse wurde das Auftreten des „außenpolitischen Naturtalents“ (Die Zeit) allgemein als gelungener Beitrag zur Versöhnung aufgenommen. In den folgenden Jahren unterstützte der Bundespräsident,
der ein überzeugter Europäer ist und sich immer wieder engagiert für das europäische Projekt ausgesprochen hat, mit seiner Autorität und Meinungsmacht die Integration der ostmitteleuropäischen Staaten in die EU.
1997 war Herzog ein weiteres mal auf einem Staatsbesuch in Polen. Die Eröffnung einer Warschauer Ausstellung zum 300. Jubiläum der Krönung Augusts des Starken zum König von Polen gab ihm die Gelegenheit, an eine weiter zurückliegende, weniger schmerzliche Epoche deutsch-polnischer Geschichte zu erinnern.