The church of the Intercession of the Holy Mother of God (the Intercession church) in Pervomaysky was first mentioned in the late XIX century in clerical journals as the church of Novobogoyavlensky Vyselki village. The church was built with the money donated by parishioners and consecrated on November 30, 1888. The church was built of stone with a bell tower and a fence. The only altar was consecrated in honor of the Intercession of the Holy Mother of God. It was a winter church where bills for heating were paid by a churchwarden.
The church functioned until the 30s of the XX century. Around this time, according to the orders made by the authorities, the church domes were taken down and the walls – destroyed. The parish school building was used to accommodate a bank and, later, a children’s library.
The rebirth of the parish began in 1992. After several stages of reconstruction, the church had acquired a symmetrical shape of a cross.
The parish boasts its Orthodox Christian library.