Железнодорожная станция, находящаяся в городе Павловский Посад, на 63 версте от Москвы, была открыта вместе с Московско-Нижегородской железной дорогой в 1861 году. В 1894 году вместе с дорогой она была принята в Государственную казну. До 1904 года станция называлась Павлово, позже - Павлово-Посад, а с 1960-х годов - по точному названию города. Возле станции сложился посёлок железнодорожников, который до начала ХХ века своей церкви не имел.
Инициатором строительства храма выступил инженер Сергей Викторович Певницкий, который перед началом строительства испросил благословения у правящего архиерея, митрополита Московского и Коломенского Владимира. Церковь строилась на основе купленного старого деревянного сруба Покровского храма, построенного в 1687 году в селе Осеченки Быковской волости Бронницкого уезда (ныне село в Раменском районе Московской области). Храм строился не только силами железнодорожников, но и на пожертвования многих жителей Павловского Посада. Посвящение церкви было выбрано в честь покровителя путешествующих Святителя Николая Мирликийского Чудотворца.
Однопрестольная тёплая деревянная шатровая церковь на каменном фундаменте построена по типу "восьмерик на четверике" в русском стиле с шатровой колокольней, крыта железом. Храм освящён Высокопреосвященнейшим Владимиром, митрополитом Московским и Коломенским 21 июля 1902 года. Бессменным священником с ноября 1903 года в храме служил Александр Георгиевич Воскресенский, весьма известный, популярный и уважаемый в Павловском Посаде человек. В 1904 году возле храма было построено министерское начальное двухклассное железнодорожное училище.
В начале 1925 года Никольская церковь была закрыта местной властью. Многочисленные ходатайства прихожан в разные инстанции о возврате храма были отклонены. ВЦИК Президиума Моссовета постановлением от 29 декабря 1925 года настоятельно рекомендовал местным органам «ускорить дело переоборудования храма в клуб...», что и было исполнено в 1926 году. Окончательно здание церкви было сломано в 1960-х годах. Сейчас на её месте незастроенная территория автовокзала.
25 ноября 2017 года на Привокзальной площади был заложен каменный храм - в память о Никольской церкви, стоявшей с 1902 года при станции Павлово.