Строительство Беломорско-Балтийского канала, начавшееся в 1931, осуществлялось силами заключенных Белбалтлага, а также привлеченных к строительным и подсобным работам спецпоселенцев-раскулаченных. «Столицей» Белбалтлага стал поселок Медвежья Гора (с 1939 – город Медвежьегорск). Здесь, помимо нескольких крупных лаготделений, дислоцировалось Управление Беломорско-Балтийского комбината НКВД и при нем – следственный изолятор, где содержались заключенные, спецпоселенцы и вольнонаемные.

Когда лесное урочище, получившее впоследствии название Сандормох (так же используется вариант названия - Сандармох), начало функционировать в качестве расстрельного полигона ББК и было ли это единственное расстрельное место в Медвежьегорском районе, в точности неизвестно. Документально установлен лишь факт расстрелов «в районе Медвежьей Горы» (так в актах о приведении приговоров в исполнение) в период Большого террора. В 1937–1938 годах здесь, в ходе «массовых операций» НКВД, по приговорам НКВД Карельской АССР, а также Комиссии НКВД и Прокуратуры СССР, расстреливали жителей Карелии и трудпоселенцев, сосланных в Карелию и здесь арестованных. Историки репрессий полагают, что значительная часть казненных могла быть расстреляна в Сандормохе. Именно в Сандормохе с 27 октября по 4 ноября 1937 были казнены 1111 заключенных Соловецкой тюрьмы особого назначения, приговоренных к расстрелу Особой тройкой УНКВД по Ленинградской области и вывезенных для этого на материк.

По окончании Большого террора использование урочища Сандормох в качестве места расстрелов и захоронений по документам не прослеживается. Поиск следов «соловецкого этапа», который десятки лет вели независимые исследователи, привел к обнаружению сандормохского захоронения. 1 июля 1997 поисковая группа Петербургского и Петрозаводского «Мемориалов», при поддержке районной администрации, обнаружила около 150 могильных ям, размером 4 × 4 метра, две из которых были вскрыты в присутствии представителя Медвежьегорской районной прокуратуры. По косвенным оценкам, в ямах было захоронено от 4 до 4,5 тысяч человек. Таким образом, стало очевидным, что в этом месте расстреляли не только «Соловецкий этап», но и то, что урочище служило расстрельным полигоном в течение продолжительного времени. После проведения необходимых исследований и получения прокурорского заключения, Общество «Мемориал» выступило с предложением создать на этом месте мемориальное кладбище. Инициатива была поддержана Правительством Карелии и администрацией Медвежьегорского района. Тогда же, в 1997, к кладбищу была проложена асфальтированная дорога, на его территории построена деревянная православная часовня Св. Георгия Победоносца, поставлены 230 надгробных знаков над могильными ямами; в центре кладбища установлены православный и католический кресты и памятник расстрелянным соловецким заключенным. Мемориальное кладбище «Сандормох» было торжественно открыто 27 октября 1997. В этот день здесь появились первые личные памятные знаки – кресты, именные таблички, надписи на надгробных памятниках, таблички на деревьях.

В наши дни на территории кладбища находится около 30 этноконфессиональных памятников (украинский, польский, финский, литовский, немецкий, еврейский, эстонский, мусульманский, вайнахский и мн. др.) и около 400 личных памятных знаков. Мемориал имеет статус памятника истории и культуры (постановление Правительства Республики Карелия №214-П от 08.08.2000). С 1998 на Мемориальном кладбище «Сандормох» ежегодно 5 августа проводятся Международные дни памяти, на которые собираются сотни людей – жители района и республики, а также разных регионов России, делегации общественных организаций из Украины, Карелии, Татарстана и др. В траурных церемониях принимают участие представители дипломатического корпуса ряда европейских стран. Имена погибших опубликованы в Книгах памяти «Поминальные списки Карелии, 1937–1938» и «Место расстрела Сандармох».