In 1889, a wooden church was built at the Rtishchevo station of the Russian Railways in honor of Saint Prince Alexander Nevsky. The funds for its construction were raised through donations from railway workers and private individuals in memory of the miraculous deliverance of the royal family. The church, located near the railway school, was opened on October 15, 1889. The consecration was performed by Bishop Pavel, who arrived with the clergy in Rtishchevo on October 14. The church was small, wooden, brick-faced, and connected to the educational institution. Inside, there was an entrance hall with coat racks and a candle box. From the entrance hall, two doors led: one to the church, the other to the school. The school was a spacious room that merged with the church during services through double doors.

Most of the items and icons in the church were donated by private individuals. A graceful chandelier, also a gift, hung in the center. The iconostasis contained works from the Imperial Academy of Arts. Among the donors was A. N. Izmailov, the head of the Tambov-Saratov railway, who contributed 300 rubles and donated church supplies. The idea for the construction belonged to the station master A. P. Sleptsov. A total of about 8,000 rubles was raised for the construction.

In 1911, a stone church, designed for 780 people, was built next to the wooden church with funds from the Russian Railways Society.

In December 1923, the Komsomol members of Rtishchevo demanded the closure of the church, and in January 1924, their request was granted. The building was handed over to trade union organizations to create a workers' club named after V. I. Lenin and a library. The club hosted 10 circles and a theater. After the Palace of Culture opened in 1935, the club was closed, and the building was occupied by station departments, leading to its decline. In 1937, the building was transferred to the aeroclub, which placed a training aircraft there. In 1940, it was used as a garage, and in 1941, as workshops and a staging commandant's office.

On May 20, 1944, the Council of People's Commissars of the USSR allowed the opening of an Orthodox church in Rtishchevo. On June 23, 1944, the building was handed over to the believers. On July 1, 1944, the church reopened. The rector became Ivan Nikolayevich Varin, with priest Ivan Petrovich Kuznetsov and protodeacon Alexander Vasilyevich Kolchev. Although the agreement provided for the transfer of the entire complex, the watchman's lodge was occupied by the gas pipeline construction department until the end of 1945.

From 1955 to 1967, the rector was protodeacon Savva Kotlyarov, the father of Metropolitan Vladimir. The future metropolitan served in the church as a reader. His mother is buried in Rtishchevo.

In the early 1990s, the church's domes were restored, and in the late 1990s, the bell tower. Today, the building is recognized as a monument of architecture and art. From 2003 to 2005, major repairs were carried out. On February 21, 2006, an icon with a particle of the relics of Saint Alexander Nevsky was delivered to the church from the Alexander Nevsky Lavra.