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 Starobielsku przetrzymywani byli oficerowie Wojska Polskiego – rezerwy, służby stałej i w stanie spoczynku oraz wyżsi urzędnicy wojskowi i państwowi. Jeńcy ze Starobielska zostali zabici w siedzibie Zarządu Obwodowego NKWD w Charkowie, następnie ich ciała ukryto w Piatichatkach pod Charkowem (obecnie część miasta).

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 Charkowie miało miejsce 17.06.2000 r.

W Charkowie wspólny Cmentarz Ofiar Totalitaryzmu zajmuje powierzchnię 2,31 ha. Znajdują się tam mogiły zbiorowe: 15 z nich to groby ofiar Zbrodni Katyńskiej, a 60 – obywateli radzieckiej Ukrainy różnej narodowości (m.in. Ukraińców, Rosjan, Polaków, Białorusinów, Niemców i Litwinów) – ofiar represji stalinowskich. Przy wejściu na teren cmentarza umieszczono płaskorzeźby przedstawiające polskiego orła wojskowego i godło ukraińskie. Ważnym elementem założenia cmentarnego jest wyłożona kostką bazaltową „czarna droga”. Na cmentarzu usytuowano dwie ściany ołtarzowe z nazwiskami: polską, poświęconą jeńcom Starobielska i ukraińską, na której upamiętniono 2746 znanych z nazwiska obywateli radzieckich. Bliżej polskiej ściany ołtarzowej, wzdłuż drogi, na niskiej podmurówce znajduje się obecnie 3811 indywidualnych tabliczek epitafijnych jeńców obozu w Starobielsku. Obok ołtarza umieszczono tablicę z inskrypcją: W hołdzie ponad 4300 oficerom WP, jeńcom wojennym obozu w Starobielsku i sowieckich więzień, zamordowanym przez NKWD wiosną 1940 r. w Charkowie. 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.

Cmentarz jest pod opieką Rady Miejskiej Charkowa. W 2004 roku Rada OPWiM, po opracowaniu biogramów do Księgi Cmentarnej i po otrzymaniu od rodzin sprostowań, wymieniła 815 tabliczek epitafijnych, usunęła 6 i dodała 24 nowe. W 2010 r. na cmentarzu przeprowadzono prace remontowe i konserwacyjne na zlecenie Rady OPWiM. Podczas działań wojennych wynikających z agresji Rosji na Ukrainę 24.02.2022 r., w marcu 2022r . na teren cmentarza spadła bomba, wystrzelona przez wojska rosyjskie, która uszkodziła jedną z mogił zbiorowych i część tabliczek epitafijnych.

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