As a result of the decision of the Political Bureau of the Central Committee of the Communist Party of the Soviet Union (b) of 5 March 1940, in the spring of 1940 the NKVD murdered around 22,000 Polish citizens: prisoners of war taken prisoner after the USSR's aggression against the eastern territories of the Second Polish Republic in September 1939; they were imprisoned in three special NKVD camps (Kozelsk, Ostashkov and Starobielsk) and prisons in so-called Western Belarus and so-called Western Ukraine. In Starobielsk, officers of the Polish Army - reserve, permanent service and retired, as well as senior military and government officials - were held. The prisoners of war from Starobielsk were killed at the headquarters of the NKVD Regional Board in Kharkiv, then their bodies were hidden in Pyatichatky near Kharkiv (now part of the city).

A dignified commemoration of the victims of the Katyn Massacre was sought by the families of the murdered in Poland and around the world, associated in associations grouped primarily in the Federation of Katyn Families and the All-Poland Association "Police Family 1939". Representatives of the Katyn circles cooperated with the Council for the Protection of Remembrance of Struggle and Martyrdom, the institution responsible on behalf of the Polish state for the commemoration of the murdered, which led to the construction in 1999-2000 of Polish War Cemeteries in Katyn, Mednoye and Kharkiv, and in 2012. - Polish War Cemetery in Kyiv-Bykivnia. The ceremonial opening and consecration of the cemetery in Kharkiv took place on 17.06.2000.

. In Kharkiv, the common Cemetery of Victims of Totalitarianism covers an area of 2.31 hectares. It contains mass graves: 15 of them are graves of victims of the Katyn Massacre, and 60 of them are graves of Soviet Ukrainian citizens of various nationalities (including Ukrainians, Russians, Poles, Belarusians, Germans and Lithuanians) - victims of Stalinist repression. At the entrance to the cemetery there are bas-reliefs depicting the Polish military eagle and the Ukrainian coat of arms. An important element of the cemetery's layout is a "black road" paved with basalt blocks. Two altar walls with names are located in the cemetery: the Polish one, dedicated to the prisoners of Starobelsk, and the Ukrainian one, commemorating 2746 Soviet citizens known by name. Closer to the Polish altar wall, along the road, on a low foundation, there are now 3811 individual epitaph plaques of prisoners of the Starobelsk camp. Next to the altar is a plaque with the inscription: In tribute to more than 4,300 Polish Army officers, prisoners of war from the Starobielsk camp and Soviet prisons, murdered by the NKVD in the spring of 1940 in Kharkiv. Polish nation. The necropolis included the following elements made of cast iron: an altar with a cross and an altar wall on which the names of the victims are engraved, a memorial bell, obelisks with the national emblem, the Virtuti Militari Cross and the Cross of the September Campaign. Signs of the four religions professed by the citizens of the Second Republic of Poland (the Latin cross, the Orthodox cross, the Star of David and the Muslim crescent) are placed in the cemetery. The Polish character of the cemeteries is emphasised by bas-reliefs depicting Polish military eagles placed at the entrance and trilingual information boards installed in 2010. Each of those buried has an individual epitaph plaque containing: military rank or service rank, name and surname, date and place of birth, occupation, service assignment, year of death.

The cemetery is under the care of the Kharkiv City Council. In 2004, the OPWiM Council, after compiling the biographies for the Cemetery Book and receiving corrections from the families, replaced 815 epitaph plates, removed 6 and added 24 new ones. Repair and maintenance work was carried out at the cemetery in 2010 on behalf of the OPWiM Council. During hostilities resulting from Russia's aggression against Ukraine on 24.02.2022, a bomb, launched by Russian troops, fell on the cemetery in March 2022, damaging one of the mass graves and some of the epitaph plaques.

For more information on the discovery of the mass graves and the construction of the cemetery, visit https://katyn.miejscapamieci.gov.pl.