В 1988 году по инициативе зарождающегося общества «Мемориал», журнала «Огонек» и других организаций в несколько этапов был проведен конкурс на национальный памятник жертвам политических репрессий в СССР. Присланные проекты памятника демонстрировались на нескольких выставках, однако лучший проект так и не был выбран. Параллельно с идеей памятника на конкурсной основе в «Мемориале» возникла идея установить камень с Соловков: с 1923 года там находился Соловецкий лагерь особого назначения, куда большевики сослали своих политических противников – именно к традиции памяти и сопротивления «политрежимных» заключенных, сохранявших память о погибших соратниках на соловецких глыбах, и отсылает Соловецкий камень в Москве. При поддержке Моссовета памятник установили на символическом месте – на Лубянской площади, рядом с зданием спецслужб и поблизости от памятника Дзержинскому, который был снесен только через 9 месяцев. Памятник был открыт в день политзаключенного, ставший днем памяти жертв политических репрессий, в шествии и митинге в день открытия приняли участие несколько десятков тысяч человек, некоторые из которых были задержаны ОМОНом. С тех пор каждый год 30 октября и в другие дни здесь проходили мемориальные акции и митинги, а с 2007 года каждое 29 октября проводится акция «Возвращение имен».