Jedną z konsekwencji 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. 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 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 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 podali 13 kwietnia 1943 r. To dziś symboliczna rocznica zbrodni. 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 niestety 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 powodu 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. Później jednak 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-u 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 w Warszawie 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 komisarza 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 ZSRR 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 ZSRR 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ą. 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. Mimo że strona rosyjska przyznała się do odpowiedzialności za zbrodnię katyńską nadal pojawiają się w Rosji głosy to kwestionujące. Jednym z ostatnich tego przykładów jest stanowisko z początku 2010 r. frakcji Komunistycznej Partii Federacji Rosyjskiej (KPRF) w Dumie Państwowej, która powołania komisji parlamentarnej do zbadania okoliczności śmierci polskich oficerów wziętych do niewoli w 1939 roku przez Armię Czerwoną. Według komunistycznych parlamentarzystów, polskich oficerów rozstrzelali hitlerowcy po zajęciu Smoleńska w 1941 roku, a nie NKWD - w 1940 roku. Deputowani z KPRF przekonują, że społeczna komisja historyków, która działała pod ich egidą, zebrała dowody świadczące o winie Niemców.