Первая деревянная церковь святой Екатерины на Старо-Петергофском проспекте была сооружена в 1721 году в деревне Калинкино. По распоряжению Екатерины II её перевели ближе к Старо-Калинкину мосту.
К 1820-м годам старый храм пришёл в полную ветхость. Прихожане обратились к властям с просьбой разрешить построить новую каменную церковь и выделить на это средства. На записке Комитета министров по этому поводу Николай I 14 июня 1827 года написал: "Составить конкурс и сделать новые проекты, ибо ни который из представленных не удовлетворителен". [Цит. по: 1, с. 83]
На организованный архитектурный конкурс представили свои проекты профессора Академии художеств А. А. Михайлов и А. И. Мельников. Оба зодчих видели новый храм в традиционном для того времени классическом стиле. Михайлов предусматривал необходимость сметы около 1 200 000 рублей, что значительно превышало выделенную сумму. По требованию императора он переработал проект, после чего смета сократилась до 500 000. Мельников предлагал проект со сметой стоимостью около 225 000 рублей, к тому же он больше понравился прихожанам. Но Николай I отверг все два варианта. По его словам "Проект г. Мельникова столько мало приличен и красив, что обезобразил бы весь квартал: надо велеть сделать другой, простой и красивый, который не превосходил бы сей же суммы". [Цит. по: 1, с. 83]
Президент Академии художеств А. Н. Оленин получил от петербургского генерал-губернатора пожелание императора найти нового архитектора. Выбор пал на Константина Андреевича Тона, который совсем недавно вернулся из заграничной командировки и был зачислен в штат академии.
Эскизный проект Тон предоставил в ноябре 1830 года. По его расчётам стоимость строительства нового храма святой Екатерины должна была составить 278 000 рублей. В конце ноября Николай I одобрил проект, но поручил сократить смету до 225 000. Причиной успеха Тона стало то, что он выбрал для новой церкви "национальный русский стиль". В проекте он использовал крестово-купольную композиционную систему, фасадам придал мотивы русской архитектуры XV-XVII веков: килевидные кокошники и закомары, узкие арочные окна, декоративную аркатуру на тонких колонках. Именно такими видел новые храмы и Николай I. В "национальных" архитектурных формах император нашёл их соответствие идейно-эстетической концепции народности, которая тогда становилась очень важной в официальной идеологической программе. Судьбу проекта Тона характеризует письмо министра императорского двора князя П. М. Волконского президенту Академии художеств А. Н. Оленину:
Строительство церкви святой Екатерины, названной по своему местоположению также Екатерингофской, велось с 1831 по 1837 год.
В советское время храм был уничтожен. На его месте было построено здание кинотеатра "Москва".
