Деревянную церковь на этом месте построили в 1649 году и освятили в честь святого Николая Мирликийского. В том же веке деревянный храм сгорел, а на его месте на средства прихожан в 1686 году был построен новый каменный храм. Церковь именовалась по местности — «на Щепах», поскольку неподалёку располагался Государев дровяной (Щепной) двор, где изготавливались срубы для деревянных дворцовых зданий.

Во время пожара 1812 года церковь серьёзно пострадала, и её здание восстанавливали на народные средства, добавив к существующему приделу второй, освящённый во имя апостолов Петра и Павла. Кроме того, в 1813 году была сооружена колокольня, которая сохранилась и до наших времен. В 1882 году по проекту архитектора Николая Финисова был построен северный придел церкви.

В 1934 году храм был закрыт для богослужений, а несколькими годами позже разграблен и перестроен почти до неузнаваемости: были снесены купола и верхняя часть колокольни, а также ликвидировано церковное кладбище. Внутренние помещения храма были перестроены под производственные цеха, где в годы Великой Отечественной войны наладили выпуск боеприпасов, а затем, до 1990-х годов, располагался завод производственного объединения «Художественная гравюра». В 1993 году здание было возвращено церкви. Богослужения возобновлены в 1994 году, а с 1999 по 2002 год проходила масштабная реконструкция здания с восстановлением башен, куполов и колокольни.

По храму Николая на Щепах (не позднее XIX века) были названы ныне существующие Первый и Второй Николощеповские переулки, а также Третий Николощеповский переулок, который в 1957 году был переименован в проезд Шломина.