The Cossack cemetery appeared in the eastern part of the Cossack suburb in the second third of the 19th century. Burial plots were allocated for the cadet corps, as well as for Catholic and cholera cemeteries. During the Great Patriotic War, soldiers who died in Omsk hospitals were buried here. The cemetery was located at the end of Nikolsky Avenue (now Krasny Zory Street) behind Shkroevskaya Street (modern Kuybyshev Street).

Initially, a chapel was built at the cemetery, and in 1859, a stone church was erected in the center of the cemetery with funds from Omsk's mayor Vladimir Petrovich Kuznetsov. In the work on Siberian icon painting by Archpriest Alexander Sulotsky, it is mentioned that the icons for the iconostasis of the Cemetery Church, as well as for the churches in Karkaral and Kuldzha, were ordered by V.P. Kuznetsov in Moscow. The interior of the church was adorned with a crystal chandelier, gifted by V.P. Kuznetsov. As mayor, V.P. Kuznetsov built a new Ilyinsky Bridge over the Om River according to the project of E.I. Ezet. He passed away on March 29, 1870. The Governor-General of Western Siberia A.P. Khrushchov requested permission from the Archbishop of Siberia and Tobolsk to bury V.P. Kuznetsov in the Cemetery Church, but Archbishop Varlaam refused, citing legislative prohibitions.

The church has not survived, but its photographs allow us to determine the style as an official direction in the 'Russian style'. The temple was built of red brick, plastered and whitewashed, and had a three-part composition. The single-domed church was decorated with classical pilasters and an entablature, while the drum of the dome and the framing of the window openings were made in the form of keel-shaped arches. The octagonal tent bell tower had one tier of bells. It is possible that the project author of the church was architect Gavriil Stepanovich Vershinin. In 1896, a narthex and bell tower were added with funds from merchant Grigory Vasilyevich Shkroev, allowing for a capacity of 400 people.

On the church holiday, a procession was held through the cemetery. There was a memorial chapel at the church. In the cemetery almshouse in 1914, seven women lived. The rectors of the church were well-known Omsk preachers: in the 1900s, Archpriest Vasily Plyaskin, and in the 1910s, Archpriest Mikhail Orlov.

During World War I, deceased soldiers and refugees were given free funerals. Notable residents of Omsk were buried near the church: Lieutenant General V.S. Tsytovich, Archpriest and Church historian A.I. Sulotsky, architect I.G. Khvorinov, merchants V.P. Kuznetsov, G.V. Shkroev, S.S. and F.S. Volkova, S.N. Moskalyitin, O.V. and V.T. Razumovsky, later Doctor F.I. Bill, scientist P.L. Dravert, Professor N.D. Liberov.

Since 1920, the church became a parish church. The parish was one of the largest in Omsk: in 1926, there were 89 people, and in 1927, 312. In 1937 and 1938, there were 30 parishioners, served by priests Kiselev and Tatiyshev, with A.M. Sukovatitsina as the community chairperson. The church was closed in February 1938, and a 'Vodnik' warehouse was placed in it.

During the Great Patriotic War, numerous requests from believers to reopen the All Saints Church in Omsk were rejected, citing that it was located a kilometer from the functioning church, which was untrue, as the Cross Exaltation Church was on the other bank of the Om River, far from the Cossack cemetery.

The fate of the All Saints Church concerned A.F. Palashenkov, an employee and later director of the local history museum. In 1948, he attempted to open a museum of the history of Omsk in the church building. In a petition dated April 10, 1949, Andrey Fedorovich indicated that the Omsk museum had a large collection of plans, drawings, photographs, and items that had nowhere to be exhibited. The city council decided to transfer the church for the museum's placement and sent a request to the Council of Ministers of the USSR. However, the initiative was unsuccessful. The Council for the Affairs of the Russian Orthodox Church under the Council of Ministers of the USSR decided on May 9, 1949: 'Consider it untimely to use the cemetery church for a museum.' In the last years, the church stood empty and gradually fell into disrepair.

On January 31, 1966, the founding conference of the regional branch of the All-Russian Voluntary Society for the Protection of Historical and Cultural Monuments took place, which made a significant contribution to the preservation of local monuments. But even during this period, there were losses: in 1975, the All Saints Church at the Cossack cemetery was demolished. On the cemetery grounds, children's and infectious hospitals were built.

At the end of 2004, at the initiative of the governor of the Omsk region L.K. Polezhaev, a new wooden church in the name of All Saints was erected at this historical site. Metropolitan Theodosius of Omsk and Tara consecrated the church and held the first liturgy on January 7, 2005, on Christmas Day.