Jedną z konsekwencji polsko-sowieckiego układu był dekret Prezydium Rady Najwyższej ZSRR z 12 sierpnia o tzw. amnestii dla "wszystkich obywateli polskich, pozbawionych obecnie wolności na terytorium sowieckim w charakterze jeńców wojennych lub na innych wystarczających podstawach". Tego samego dnia Biuro Polityczne KC WKP(b) podjęło decyzję nakazującą zwolnienie "wszystkich jeńców wojennych i internowanych wojskowych byłej armii polskiej". Strona polska liczyła na to, że liczba ludności polskiej przebywającej na obszarze sowieckiego państwa pozwoli utworzyć armię złożoną z co najmniej 200 tys. żołnierzy. Problemem pozostawała kadra oficerska. Gen. Władysław Anders otrzymał listę zawierającą jedynie nazwiska 1658 oficerów polskich przetrzymywanych przez władze sowieckie. Lista wręczona mu przez przedstawiciela NKWD nie mogła być dłuższa, gdyż pozostali oficerowie wiosną 1940 r. zostali przez NKWD zamordowani, o czym w tym czasie strona polska nie wiedziała. Na początku września 1941 r. ambasador polski w ZSRR Stanisław Kot wręczył zastępcy ludowego komisarza spraw zagranicznych Związku Sowieckiego Andriejowi Wyszyńskiemu pierwszą listę zaginionych. W ciągu następnych miesięcy ambasador Kot wielokrotnie bezskutecznie interweniował u Wyszyńskiego w sprawie odnalezienia polskich jeńców wojennych. Obok działań o charakterze dyplomatycznym, władze polskie podjęły działania wywiadowcze. Już we wrześniu-październiku 1941 roku w okupowanej Polsce, z rozkazu gen. Władysława Sikorskiego, poszukiwano zaginionych jeńców z Kozielska, Starobielska i Ostaszkowa, którzy według Sowietów zostali rzekomo zwolnieni. W wyniku poszukiwań nie odnaleziono żadnego z jeńców ani w domach, ani w niemieckich oflagach. Gen. Sikorski w czasie wizyty na Kremlu 3 grudnia 1941 r., w obecności gen. Władysława Andersa i komisarza spraw zagranicznych Wiaczesława Mołotowa, usłyszał od Stalina, że polscy oficerowie "uciekli do Mandżurii". Był to początek długiej historii kłamstwa katyńskiego. Informację o odkryciu masowych grobów w Katyniu Niemcy podawali w dniach 11-13 kwietnia 1943 r. W odpowiedzi, Sowieckie Biuro Informacyjne ogłosiło 15 kwietnia 1943 r., że polscy jeńcy byli zatrudnieni na robotach budowlanych na zachód od Smoleńska i "wpadli w ręce niemieckich katów faszystowskich w lecie 1941 r., po wycofaniu się wojsk sowieckich z rejonu Smoleńska". Komunikat stwierdzał: "Niemieckie zbiry faszystowskie nie cofają się w tej swojej potwornej bredni przed najbardziej łajdackim i podłym kłamstwem, za pomocą którego usiłują ukryć niesłychane zbrodnie, popełnione, jak to teraz widać jasno, przez nich samych". Po zajęciu Smoleńska pod koniec września 1943 r. przez Armię Czerwoną władze sowieckie powołały specjalną komisję do przeprowadzenia dochodzenia w sprawie Katynia pod przewodnictwem prof. dr. Nikołaja Burdenki. 24 stycznia 1944 r., po ekshumacji 925 odpowiednio spreparowanych ciał polskich oficerów, wspomniana komisja ogłosiła, że zbrodni na Polakach dokonali Niemcy między wrześniem a grudniem 1941 r. W sprawie katyńskiej Polacy nie uzyskali wsparcia ze strony przywódców mocarstw zachodnich, którzy, w imię trwałości wojennego sojuszu ze Stalinem, okazywali mu pomoc w ukrywaniu prawdy o tej zbrodni. W 1945 r. w trakcie procesu zbrodniarzy nazistowskich w Norymberdze Sowieci wprowadzili do aktu oskarżenia zarzut odpowiedzialności za zbrodnię katyńską. Trybunał Norymberski w wydanym w 1946 r. wyroku pominął jednak sprawę zamordowania polskich oficerów z braku dowodów. Po wojnie przez całe lata propaganda sowiecka i peerelowska nadal twierdziły, że sprawcami zbrodni katyńskiej byli hitlerowcy. Do 1956 r. władze PRL mówiły o "perfidnej niemieckiej prowokacji w Katyniu". Potem samo słowo Katyń zniknęło całkowicie; przez lata cenzura wykreślała je z każdej publikacji. Następnie znów przedstawiano zakłamaną wersję wydarzeń. W 1983 r. w Katyniu wzniesiono sowiecki pomnik z napisem: "Ofiarom faszyzmu - oficerzom (sic) polskim, rozstrzelanym przez hitlerowców 1941 r.". Z kolei władze PRL w 1985 r. - w miejsce pierwszego w Polsce pomnika ku czci ofiar Katynia, podającego nazwy: Ostaszków, Starobielsk, Katyń oraz 1940 r. jako datę dokonania zbrodni - odsłoniły w "Dolince Katyńskiej" na Cmentarzu Wojskowym na Powązkach pomnik z napisem: "Żołnierzom polskim ofiarom hitlerowskiego faszyzmu spoczywającym w ziemi katyńskiej - 1941 rok". Większość społeczeństwa polskiego nigdy jednak w te kłamstwa nie uwierzyła. W świadomości Polaków Katyń był zbrodnią Sowietów, a pamięć ich ofiar była przypominana na różne sposoby. W "Dolince Katyńskiej" przez wszystkie te lata zapalano znicze i składano kwiaty. 21 marca 1980 r., protestując "przeciw zmowie milczenia wokół zbrodni w Katyniu", były żołnierz AK Walenty Badylak dokonał aktu samospalenia na Rynku Głównym w Krakowie. W 40. rocznicę zbrodni katyńskiej, 11 kwietnia 1980 r. KSS KOR wydał oświadczenie wyrażające przekonanie, że ujawnienie stalinowskich zbrodni wobec obywateli polskich "będzie istotnym krokiem w kierunku braterstwa i przyjaźni z narodem rosyjskim". Za szerzenie w PRL "kłamstwa katyńskiego" przeprosił Polaków w 2000 r. ówczesny prezydent Aleksander Kwaśniewski. Związek Sowiecki do zbrodni katyńskiej przyznał się dopiero 13 kwietnia 1990 r. Wówczas to w komunikacie rządowej agencji TASS oficjalnie potwierdzono, że polscy jeńcy wojenni zostali rozstrzelani wiosną 1940 r. przez NKWD. Jako winnych wskazano wówczas szefa NKWD Ławrientija Berię i jego zastępcę Wsiewołoda Mierkułowa. Strona sowiecka wyraziła głębokie ubolewanie w związku z tragedią katyńską, nazywając ją "jedną z cięższych zbrodni stalinizmu". Tego samego dnia prezydent ZSRS Michaił Gorbaczow przekazał prezydentowi RP Wojciechowi Jaruzelskiemu kopie archiwalnych dokumentów z listami więźniów skierowanych w kwietniu i maju 1940 r. z obozu jenieckiego w Kozielsku do Smoleńska i z obozu w Ostaszkowie do Kalinina (obecny Twer), a także wykaz akt ewidencyjnych jeńców wojennych, którzy opuścili obóz NKWD w Starobielsku. Prezydent ZSRS oficjalnie polecił wówczas wyjaśnić sprawę katyńską. Pomimo upływu lat strona rosyjska nie rozstrzygnęła w sposób ostateczny kwalifikacji prawnej zbrodni. Prokuratura rosyjska uznała ją za przestępstwo pospolite. Nie ujawniła prawnego uzasadnienia, tłumacząc się tajemnicą śledztwa. Nadal nie wyjaśniono wielu istotnych kwestii dotyczących okoliczności zbrodni, np. nie ustalono nazwisk wszystkich ofiar. Nie odnaleziono dotychczas listy więźniów zamordowanych na Białorusi (tzw. białoruska lista katyńska). Nie znamy również dokładnej liczby rozstrzelanych oraz dat śmierci i wszystkich miejsc pochówku osób straconych na mocy decyzji Biura Politycznego KC WKP(b) z 5 marca 1940 r. Strona polska wciąż oczekuje na pełną rehabilitację ofiar oraz na ustalenie i opublikowanie nazwisk inicjatorów i wykonawców zbrodni. 26 listopada 2010 r. Duma Państwowa, izba niższa rosyjskiego parlamentu, przyjęła uchwałę w sprawie zbrodni katyńskiej. Mord na polskich oficerach wiosną 1940 r. uznano w niej za zbrodnię reżimu stalinowskiego.