В декабре 1995 обострились наиболее конфликтные после 1989 проблемы в Польше. Сейм обсуждал закон о люстрации, требовавший выяснения возможных связей с тайной полицией претендентов на государственные должности. В декабре 1995 премьер-министр Юзеф Олекса (Союз демократических левых сил) был обвинен министром внутренних дел Анджеем Милчановским в том, что он в течение многих лет работал на советскую, а затем на российскую разведку. Под давлением общественности Олекса ушел в отставку в январе 1996, и его сменил Влодзимеж Чимошевич. Дело Олексы стало толчком для решения вопроса о люстрации. В августе 1997 парламент принял соответствующий закон, но не смог ввести его в действие. В октябре 1998, президент А.Квасьневский подписал закон о люстрации. В соответствии с ним все высшие чиновники, депутаты парламента и судьи должны были сообщить о том, сотрудничали ли они ранее с органами безопасности. Виновных в таком сотрудничестве не вынуждали прекращать политическую деятельность, но их признания должны были доводиться до сведения общественности. Тем же лицам, которые скрывали правду о своей причастности к органам безопасности, в случае ее обнаружения запрещалось занимать высокие государственные должности в течение 10 лет.

Польское правительство поддержало военную акцию НАТО против Югославии в 1999, хотя опросы общественного мнения продемонстрировали сдержанное отношение к этой акции, а церковные иерархи выступали с ее осуждением. Страна готовилась к вступлению в ЕС, при этом прогнозировались как позитивные (рост ВВП, сдерживание инфляции), так и негативные (увеличение торгового дефицита, рост безработицы) последствия данного шага. Президент Квасьневский подчеркивал необходимость укрепления экономических связей с Россией и другими странами Восточной Европы.