Внаслідок рішення Політбюро ЦК ВКП(б) від 5 березня 1940 року, навесні 1940 року НКВС знищив близько 22 000 польських громадян: військовополонених, які потрапили в полон після агресії СРСР на східні території Другої Речі Посполитої у вересні 1939 року; вони були ув'язнені в трьох спеціальних таборах НКВС (Козельськ, Осташків і Старобільськ) і в'язницях на території так званої Західної Білорусі і так званої Західної України. У Старобільську утримувалися офіцери Війська Польського - запасу, постійної служби та у відставці, а також вищі військові та урядовці. Військовополонені зі Старобільська були вбиті в штаб-квартирі обласного управління НКВС у Харкові, потім їхні тіла були заховані в П'ятихатках під Харковом (нині частина міста).

Гідного вшанування пам'яті жертв Катинського розстрілу домагалися родини вбитих у Польщі та в усьому світі, об'єднані в асоціації, насамперед у Федерацію катинських родин та Всепольське об'єднання "Поліційна родина 1939". Представники катинських кіл співпрацювали з Радою охорони пам'яті боротьби і мучеництва - інституцією, відповідальною від імені польської держави за вшанування пам'яті вбитих, що призвело до спорудження у 1999-2000 роках польських військових цвинтарів у Катині, Мєдному та Харкові, а у 2012 році - у Києві. - Польський військовий цвинтар у Києві-Биківнянському.

Урочисте відкриття та освячення цвинтаря в Харкові відбулося 17.06.2000 р.. У Харкові загальне кладовище жертв тоталітаризму займає площу 2,31 га. На ньому знаходяться масові поховання: 15 з них - могили жертв Катинського розстрілу, 60 - могили радянських громадян України різних національностей (в тому числі українців, росіян, поляків, білорусів, німців і литовців) - жертв сталінських репресій. При вході на цвинтар знаходяться барельєфи із зображенням польського військового орла та українського герба. Важливим елементом планування цвинтаря є "чорна дорога", вимощена базальтовими блоками. На кладовищі розташовані дві вівтарні стіни з іменами: польська, присвячена в'язням Старобільська, та українська, на якій поіменно вшановано 2746 радянських громадян, відомих поіменно. Ближче до стіни польського вівтаря, вздовж дороги, на невисокому фундаменті, зараз знаходяться 3811 індивідуальних епітафійних плит старобільських військовополонених. Поруч з вівтарем знаходиться табличка з написом: В пам'ять про понад 4300 офіцерів Війська Польського, військовополонених зі Старобільського табору і радянських в'язниць, вбитих НКВС навесні 1940 року в Харкові. Польська нація. Некрополь включав наступні елементи, виготовлені з чавуну: вівтар з хрестом і вівтарною стіною, на якій викарбувані імена жертв, меморіальний дзвін, обеліски з державним гербом, Хрестом Virtuti Militari і Хрестом Вересневого походу. На кладовищі розміщені знаки чотирьох релігій, які сповідували громадяни Другої Речі Посполитої (латинський хрест, православний хрест, зірка Давида та мусульманський півмісяць). Польський характер кладовищ підкреслюють барельєфи із зображенням польських військових орлів, розміщені при вході, та тримовні інформаційні таблички, встановлені у 2010 році. Кожен похований має індивідуальну меморіальну дошку, на якій вказані: військове звання або посада, ім'я та прізвище, дата і місце народження, рід занять, місце служби, рік смерті.

Кладовище знаходиться під опікою Харківської міської ради. У 2004 р. Рада ОПВіМ, склавши біографії для Цвинтарної книги та отримавши поправки від родин, замінила 815 епітафійних плит, зняла 6 і додала 24 нових. У 2010 році від імені Ради ОПВіМ на цвинтарі були проведені ремонтні та профілактичні роботи. Під час бойових дій внаслідок агресії Росії проти України 24.02.2022 р. на цвинтар у березні 2022 р. впала бомба, запущена російськими військами, пошкодивши одну з братських могил та частину епітафій.

Більше інформації про виявлення масових поховань та будівництво кладовища можна знайти на сайті https://katyn.miejscapamieci.gov.pl.