W wyniku decyzji Biura Politycznego KC WKP(b) z dnia 5 marca 1940 roku NKWD wiosną 1940 roku wymordowało około 22 000 obywateli polskich: jeńców wojennych wziętych do niewoli po agresji ZSRR na wschodnie tereny II Rzeczypospolitej we wrześniu 1939 roku; osadzeni oni byli w trzech obozach specjalnych NKWD (Kozielsk, Ostaszków i Starobielsk) oraz więzieniach tzw. Zachodniej Białorusi i tzw. Zachodniej Ukrainy. W Ostaszkowie przetrzymywani byli funkcjonariusze Policji Państwowej, Policji Województwa Śląskiego, Straży Granicznej, Straży Więziennej, Korpusu Ochrony Pogranicza, wywiadu i kontrwywiadu, żandarmi i osadnicy wojskowi. Jeńców z Ostaszkowa zamordowano w siedzibie Zarządu Obwodowego NKWD w Kalininie (obecna nazwa: Twer), a ich ciała ukryto w tzw. dołach śmierci w Miednoje.

O godne upamiętnienie ofiar Zbrodni Katyńskiej zabiegały rodziny zamordowanych w Polsce i na świecie, zrzeszone w stowarzyszeniach skupionych przede wszystkim w Federacji Rodzin Katyńskich oraz w Ogólnopolskim Stowarzyszeniu „Rodzina Policyjna 1939”. Przedstawiciele środowisk katyńskich współpracowali z Radą Ochrony Pamięci Walk i Męczeństwa, instytucją odpowiedzialną z ramienia państwa polskiego za upamiętnienie zamordowanych, która doprowadziła do wybudowania w latach 1999-2000 Polskich Cmentarzy Wojennych w Katyniu, Miednoje i Charkowie oraz w 2012 r. – Polskiego Cmentarza Wojennego w Kijowie-Bykowni. Uroczyste otwarcie i poświęcenie cmentarza w Miednoje miało miejsce 2.09.2000 r.

Na cmentarzu zajmującym obszar 1,7 ha urządzono 25 mogił zbiorowych w miejscu pierwotnych dołów śmierci. Zostały one zaznaczone płytami, a na każdej z nich postawiono wysoki krzyż. Przy alei biegnącej wokół mogił umieszczono 6296 indywidualnych tabliczek epitafijnych. Obok ołtarza znajduje się tablica z inskrypcją: W hołdzie/ ponad 6300 spoczywającym w Miednoje/ funkcjonariuszom Policji Państwowej/ i Policji Województwa Śląskiego/ Straży Granicznej i Straży Więziennej/ żołnierzom i oficerom/ żandarmerii wojskowej/ Korpusu Ochrony Pogranicza/ i innych formacji wojskowych/ pracownikom administracji państwowej/ i wymiaru sprawiedliwości/ II Rzeczypospolitej/ jeńcom wojennym z obozu w Ostaszkowie/ zamordowanym przez NKWD wiosną 1940 r./ w Kalininie/ Naród Polski. Na terenie nekropolii znalazły się następujące elementy wykonane z żeliwa: ołtarz z krzyżem i ścianą ołtarzową, na której wyryto nazwiska ofiar, dzwon pamięci, obeliski z godłem państwowym, krzyżem Virtuti Militari i Krzyżem Kampanii Wrześniowej. Na terenie cmentarza umieszczono znaki czterech religii wyznawanych przez obywateli II RP (krzyż łaciński, krzyż prawosławny, gwiazda Dawida i muzułmański półksiężyc). Polski charakter cmentarzy podkreślają umieszczone przy wejściu płaskorzeźby przedstawiające polskie orły wojskowe oraz zamontowane w 2010 r. trójjęzyczne tablice informacyjne. Każdy z pochowanych posiada indywidualną tabliczkę epitafijną, zawierającą: stopień wojskowy lub rangę służbową, imię i nazwisko, datę i miejsce urodzenia, zawód, przydział służbowy, rok śmierci.

Polski Cmentarz Wojenny w Miednoje jest częścią rosyjskiego Kompleksu Memorialnego. W oddzielnej części upamiętniono tam obywateli radzieckich różnych narodowości (wśród nich są również Polacy), zamordowanych przez władze ZSRR w latach 1933-1938. Rosyjski Kompleks Memorialny jest pod opieką Państwowego Centralnego Muzeum Historii Współczesnej Rosji. Rada OPWiM przeprowadziła w Miednoje prace remontowe i konserwacyjne w 2010 r.

Więcej informacji na temat odkrycia masowych grobów i budowy cmentarza znajduje się na stronie internetowej https://katyn.miejscapamieci.gov.pl.