В начале XVI века на месте нынешнего храма существовал Ильинский монастырь, основанный не позднее XV века. В 1519 году началось строительство каменной церкви в честь пророка Илии, завершившееся в 1521 году. Инициатором строительства был некий Клим по прозвищу Мужило, представитель простого сословия. В честь его небесного покровителя в южной апсиде храма был устроен придел священномученика Климента. После возведения этого храма улица получила название Ильинка, а торговая площадь стала называться Ильинским крестцом.
В 1547 году храм пострадал от пожара, но был восстановлен. В 1606 году колокольня храма сыграла важную роль в восстании против Лжедмитрия I: по приказу Василия Шуйского с неё был дан набат, ставший сигналом к началу восстания. В Смутное время монастырь был упразднён, и храм стал приходским.
В 1676 году церковь вместе с прилегающей землёй была передана Новгородскому архиерейскому дому, после чего началась её реконструкция. Был надстроен верхний храм, куда перенесли престол в честь пророка Илии, а в нижнем храме освятили престол во имя апостола Тимофея. В 1820-х годах с северной стороны храма была пристроена колокольня. В 1864 году, после значительной перестройки, нижний храм был упразднён, галерея снесена, а в южной апсиде верхнего храма устроен лестничный пролёт. В результате этих изменений церковь стала частью Тёплых торговых рядов.
В 1923 году храм был закрыт, а верхний ярус колокольни разобран. С 1930 по 1980 годы здание использовалось различными учреждениями. Несмотря на это, здание храма сохранилось и является объектом культурного наследия федерального значения.
