Lata 2000–2007 thumb|Spotkanie premiera Leszka Millera z prezydentem Rosji Władimirem Putinem, 2002 Po okresie napięć pod koniec lat 90. i początku roku 2000 (wydalenie dziewięciu dyplomatów rosyjskich, pod zarzutem szpiegostwa na rzecz RosjiK. Janowski, Polska polityka zagraniczna w 1989 r. 10 lat później, Łódź 2010, .) doszło do nieznacznej poprawy w stosunkach dwustronnych. Przypisuje się to nieoficjalnej wizycie prezydenta RP Aleksandra Kwaśniewskiego w Rosji w lipcu 2000 roku. W maju 2001 roku do Polski przyjechał rosyjski premier Michaił Kasjanow. Źródłem napięć były nadal kwestie historyczne. Polska domagała się zakończenia śledztwa w sprawie zbrodni katyńskiej, a także odszkodowań i zadośćuczynienia za represje z okresu stalinowskiego. Rosja natomiast uznała, że rozliczenia z historią to już zamknięty rozdział, gdy w roku 2000 uroczyście otwarto dwa polskie cmentarze wojskowe, w Katyniu i Miednoje.