Отдельно стоящая трехъярусная шатровая колокольня была построена в 1860-х годах по проекту архитектора Н.И. Козловского. Нижний этаж монументального первого яруса в центре имеет сквозной проезд на церковный двор, на втором – храм в честь иконы Божией Матери "взыскание погибших". Второй ярус – четверик. На третьем ярусе – восьмерике – размещаются колокола. он увенчан шатром с главкой и крестом. Колокольня, построенная в русско-византийском стиле, соперничала по высоте с завершенным в 1859 году храмом Христа спасителя.

Никак не перекликаясь со зданием самой церкви Софии Премудрости Божией, она гармонирует с вертикалями кремлевских башен и колокольней Ивана великого, расположенными на другом берегу Москвы-реки. И это не случайно – колокольня должна была стать частью "софийского ансамбля", в который входило бы и соответствующее по масштабам и архитектурному облику новое здание храма. Идея возвести в центре Москвы, напротив кремля, соразмерный храму Христа Спасителя и кремлевским соборам храмовый комплекс, соименный главной святыне византийской империи – Святой Софии Константинопольской, отсылала к известной концепции "Москва – Третий Рим" и подчеркивала значение Первопрестольной как мирового оплота православия. Грандиозным планам не суждено было сбыться: архитектурная комиссия установила, что здание храма не впишется в узкий участок земли, вытянутый между рекой и обводным каналом.

Строительство колокольни продолжалось с 1862 по 1868 годы, и приходилось на период, последовавший за поражением в крымской войне и резким ослаблением позиций России. Вряд ли можно считать простым совпадением посвящение надвратного храма именно иконе Божией Матери "Взыскание погибших". В 1908 году, когда во время наводнения вода в Москве-реке поднялась почти на 10 метров, колокольня сильно пострадала.

Храм был закрыт в 1930 году. С 1960 года здание колокольни находится под государственной охраной, с 1973 года – это объект культурного наследия республиканского (в настоящее время – федерального) значения. Тем не менее почти 20 лет (с 1973 по 1992 годы) в ней размещался трест подводно-технических и строительных работ "союзподводгазстрой". В 1992 году храм, а в 1994 году и колокольня были переданы русской православной церкви. Престол надвратной церкви иконы Божией Матери "Взыскание погибших" освятили в 1995 году. 

Колокольня реставрировалась в 1960-м, затем реставрационные работы проводились в конце 70-х – начале 80-х годов. В 1998 году, по инициативе церковной общины, заслуженный художник российской Федерации, художник-реставратор первой категории Д.В. Витошнов провел первичные научно исследовательские работы по настенной живописи в интерьерах колокольни. Делая пробную расчистку фрагментов росписей в надвратной церкви, реставраторы сняли пять слоев краски. Тогда же, в конце 1990-х, начались работы по восстановлению колоколов звонницы. Но средств прихода на проведение комплексных реставрационных работ не хватало.

В 2010 году Правительство Москвы приняло решение о проведении полномасштабной реставрации колокольни. К этому моменту сохранность объекта была удовлетворительной, но реконструкции и реставрации требовали фундамент, цоколь, перекрытия, кровля, столярные заполнения, а также инженерные системы здания. Помимо укреплений фундаментов и несущих конструкций, реставрации фасадов, монтажа инженерных систем, установки нового позолоченного креста, точно соответствующего сохранившимся историческим чертежам, и колоколов проводились работы и во внутренних помещениях. Была отреставрирована чугунная лестница. Во внутренних помещениях воссозданы полы, отреставрированы поверхности сводов. В рамках этапа по восстановлению внутреннего убранства колокольни проведены консервация и реставрация лепного позолоченного декора сводов и стен.

В 2013 году колокольня стала лауреатом конкурса правительства Москвы на лучший проект в области сохранения и популяризации объектов культурного наследия "Московская реставрация 2013" в номинации: "За высокое качество ремонтно-реставрационных работ".