Несмотря на то, что в Меленках уже действовал Покровский собор, и что помещение храма было достаточно большим по размерам, тем не менее оно не могло вместить всех желающих. Возникла необходимость в строительстве нового храма. 15 сентября 1870 года был утверждён проект, а 23 мая 1871 г. после молебна приступили к закладке храма.
6 декабря 1879 г. был освящён главный престол церкви во имя святителя и чудотворца Николая и придельный с правой стороны во имя святителя Алексия, митрополита Московского, а 7 декабря 1879 г. придельный престол с левой стороны во имя преподобного Симеона Столпника. Восьмого декабря на колокольню при церкви были подняты 7 колоколов.
Как церковь, так и колокольня были «устроены в древневизантийском вкусе». Длина церкви от восточной стены до западной двери составляло 9 сажен (19,20 м), высота внутри 12 сажен (25,6 м), ширина 9 сажен (19,20 м).
До 1883 г. при церкви особого причта не было; богослужение отправлялось соборным причтом. С 1883 г. существовал особый причт, состоящий из священника и псаломщика. На содержание причта отпускалось городским обществом 500 руб. и от церковных служб получается около 700 руб. в год. Прихода при церкви не имелось.
Указом Св. Синода от 30 декабря 1908 г. за № 16848 открыт самостоятельный приход при Николаевской церкви города Меленок с существующим при ней с 1883 г. составом причта из священника и псаломщика.
В связи с постановлением Владимирского губисполкома от 20 октября 1928 г. Никольская церковь была закрыта. В помещении бывшего храма находился клуб. В 1939 г. здание бывшей церкви было разрушено. После разрушения храма, место пустовало до 1962 г., когда был построен кинотеатр «Юность», который в начале 1990-х гг. закрыли. Здание постепенно стало приходить в негодность. По причине того, что оно «ничьё», его стали приглядывать себе различные секты для своих собраний, что и послужило основным толчком для создания в 1996 г. общественного комитета, который предпринял активные действия по передаче здания Русской Православной Церкви.
Сайт Муромской епархии