Стоявшая на углу Большой Лубянки и Кузнецкого Моста церковь Введения во храм Пресвятой Богородицы была построена в XVI веке в княжение Василия III, отца Ивана Грозного. О ее постройке имеется летописное сообщение под 1514 годом, в котором идет речь о государственном строительном проекте — возведении сразу одиннадцати церквей в разных районах Москвы: «тоя же весны […] князь великий Василий Иванович всея Руси повеле заложити и сделати церкви кирпичны и камены […] да на Устретенской улице церковь Введения Святыя Богородицы, а всем тем церквем был мастер Алевиз Фрязин».
Напомним, что тогда Большая Лубянка называлась Сретенской, или Устретенской, улицей, а само место, где строилась церковь, было заселено жителями Пскова. В 1510 году, рассказывает летопись, великий князь Василий Иванович «триста семей псковичь к Москве свел […] и подавал им дворы по Устретенской улице, […] не промешал с ними ни одного москвитина». Поэтому в XVI–XVII веках к названию церкви прибавляли топографическое определение «во Псковичах».
Архитектор Алевиз Фрязин, или Алевиз Новый (называемый так в отличие от работавшего тогда же в Москве более старшего по возрасту итальянского инженера и архитектора, его тезки Алевиза Старого), был приглашен на службу еще Иваном III. Полное его имя — Алозио Ламберти да Монтаньяна. В Россию он прибыл с характеристикой «Алевиз мастер вельми добрый, не как иные мастеры, весьма великий мастер» и скоро оправдал ее на деле. Он строит систему рвов — водных укреплений вокруг Кремля, возводит в Кремле Архангельский собор, наконец, ему поручается строительство церквей, которые должны играть градообразующую роль для всего города. Автор современной работы об Алевизе Новом определяет его должность как «главного архитектора Москвы».
Из построенных тогда Алевизом Новым церквей, при проектировании которых он руководствовался как образцами владимиро-суздальских храмов, сохранилась церковь Владимира в Старых садех, стоящая на Ивановской горке, к которой сходятся четыре переулка. Этот храм представляет собой памятник замечательной красоты и стоит на таком счастливо выбранном месте, что, являясь зрительным центром окружающей разнообразной застройки, превратил этот уголок старой Москвы в один из самых привлекательных и проникновенных московских пейзажей. Недаром его часто рисуют художники.
Такую же роль в окружающем пейзаже играла и церковь Введения во храм Пресвятой Богородицы. Она стояла на высоком берегу Неглинной, видная и с реки, из заречья, и с улиц и переулков, сходившихся к ней: Лубянки, Сретенки, Кузнецкой, Ивановского переулка, который был проложен к ней с Мясницкой мимо церкви Иоанна Предтечи (с середины XVIII века этот переулок стали называть Фуркасовским). По ее местоположению в XVIII веке церковь называли также Введения,
В XVII–XVIII веках этот храм пользовался у москвичей большой известностью и почитанием, поэтому и Кузнецкий Мост от Рождественки до Лубянки в это время в Москве чаще называли Введенской улицей. Только с начала XIX века благодаря модным лавкам, которым для их владельцев и покупателей было престижней находиться на Кузнецком Мосту, чем на Введенской улице, церковное название стало вытесняться названием Кузнецкий Мост — символом суетной моды и роскоши.
Церковь Введения не раз перестраивалась и обновлялась. В начале XVII века, после освобождения Москвы от польских интервентов, князь Дмитрий Михайлович Пожарский ополченскую святыню — образ Казанской Божией Матери, с которой был совершен поход и освобождена Москва, поставил в своей приходской церкви, и она пребывала там до 1630-х годов, до построения Казанского собора на Красной площади, куда и была по завершении строительства перенесена.
В середине XVIII века обветшавшая церковь «иждивением прихожан» была капитально отремонтирована, заново выстроены трапезная и колокольня. Причем алтарная часть храма осталась не затронутой перестройкой, и позднейшие исследования подтвердили, что она относится к XVI веку.
В 1817 году прихожанин церкви антиквар и коллекционер Д. А. Лухманов обновил внутреннюю роспись храма, она была выполнена в стиле любимого им искусства Возрождения — «под Рафаэля и Рубенса».