Церковь Николы Гостинного — одна из древнейших в Коломенском кремле. Построена в 1514 году епископом Митрофаном по повелению Великого Князя Василия Иоанновича. Название церкви связывают с его назначением, поскольку он являлся патрональным для коломенского объединения купцов-гостей. Современный вид церковь приобрела после перестройки в 1848 году.
В 1655 года Антиохийский Патриарх Макарий III остановился в Коломне и из-за моровой язвы жил здесь полгода, фактически исполняя обязанности коломенского архиерея. Храм Николы Гостинного упомянут в описании Коломны архидиаконом Павлом Алеппским, секретарем Антиохийского посольства.
По сведениям 1843 года, храм имел каменное здание с колокольней с шестью колоколами, придел в честь иконы Божией Матери «Всех скорбящих Радость». К древнейшему периоду относится небольшой четверик с крестчатым сводом и граненой апсидой.
В процессе реконструкции 1848 года помимо главного алтаря во имя святителя Николая, были устроены еще два придела, в честь икон Божией Матери «Всех скорбящих Радость» и «Знамение». Сохранилось напрестольное Евангелие 1509 года, написанное для храма по заказу священника Петра Никольского.
В главном приделе находилась храмовая икона Николы Заразского. В трапезной части помещалась икона Божией Матери «Всех скорбящих Радость» и икона Божией Матери «Донская», но доска была старой, и, возможно, под записями скрывалось более древнее изображение. Кроме этих святынь, в церкви сохранился Синодик XIX века и резное изображение Страждущего Спасителя в полтора аршина высотою.
В соответствии с Приказом № 18 Заседания президиума Московского областного исполнительного комитета и Московского Совета РК и КД от 11 ноября 1929 года. Храм был закрыт. Последним священником храма был отец Василий Радугин. В начале 1930-х годов в храме помещался пересыльный пункт. До августа 2002 года в здании находилась спортивная школа.
Первая Божественная литургия состоялась 28 августа 2002 года в день Успения Пресвятой Богородицы.
