Воздвигнуть монумент создателю ВЧК было решено еще в 1936 году. Однако свои коррективы внесла Великая Отечественная война. После войны, спустя 13 лет, к этому вопросу вернулись. Власти решили, что памятник будет стоять на Лубянской площади напротив здания КГБ на месте Никольского фонтана, созданного архитектором Иваном Витали и названным так по выходящей к нему Никольской улице. Сам же фонтан был перенесен к зданию Академии наук на Ленинском проспекте.
В конкурсе на его сооружение победил скульптор Евгений Вучетич. «Железный Феликс», отлитый из бронзы, простоял на Лубянской площади 33 года. В 1990 году по инициативе общества «Московский мемориал» на Лубянскую площадь был доставлен Соловецкий камень из одноименного лагеря особого назначения как дань памяти жертвам политических репрессий. 22 августа 1991 года после подавления ГКЧП памятник Дзержинскому был демонтирован защитниками Белого дома, праздновавшими победу над путчистами.
Через три года – в 1994 году - "Железный Феликс" обрел свое пристанище в Парке скульптур на Крымском валу.
По рассказам очевидцев, когда памятник водружали на новый постамент, по его бронзовым щекам потекли слезы - это пролилась скопившаяся в глазных впадинах дождевая вода.
В последнее время возникали различные слухи и мнения о судьбе бронзового памятника. Московские власти не раз предлагали восстановить памятник основателю ВЧК на прежнем месте. Тем не менее, эту идею отклоняла комиссия по монументальному искусству Мосгордумы. Депутаты мотивировали свое решение тем, что водружение фигуры Дзержинского на Лубянке "может внести раскол в общество".
В начале ноября 2005 года в Москве во дворе здания ГУВД на Петровке, 38 по просьебе ветеранов столичной милиции был установлен бюст руководителя Феликса Дзержинского. Бюст Дзержинского стоял на Петровке с 1977 года до августа 1991. В этот год он также попал в немилость защитниками Белого дома, и его демонтировали в тот же день, когда на Лубянской площади был снят с постамента памятник Дзержинскому.
