W rezultacie polskich starań wiosną 1992 zostały podpisane z władzami obwodów smoleńskiego i twerskiego w Federacji Rosyjskiej, a w połowie lipca tego roku – także charkowskiego na Ukrainie, umowy intencyjne w sprawie wspólnych działań, których celem było wybudowanie polskich cmentarzy w Katyniu, Miednoje i Charkowie.
21 marca 1994 w Warszawie podpisana została między Rządem Rzeczypospolitej Polskiej a Rządem Ukrainy umowa o ochronie miejsc pamięci i spoczynku ofiar wojny i represji politycznych, stwarzająca podstawy formalne do przeprowadzenia ekshumacji i budowy cmentarza.
Decyzją nr 271 z 24 marca 1999 Komitet Wykonawczy Charkowskiej Rady Miejskiej wydzielił 4248 m² gruntu w VI Kwartale Parku Leśnego Radzie OPWiM oraz udzielił zezwolenia na projektowanie i zbudowanie cmentarza ofiar totalitaryzmu. 31 marca 1999 Budimex S.A. rozpoczął prace budowlane, a ponadto w tym też roku, rozstrzygnięty został przetarg na elementy rzeźbiarskie, w wyniku którego ich wykonanie, dostawę i montaż Rada OPWiM zleciła konsorcjum Budimex S.A. – Metalodlew S.A..