The church probably existed in the medieval period, during Despot Stefan Lazarević's reign in Belgrade (1402–1427), but the exact circumstances about its construction - when it was built and by whom - are unknown.

Urban myth developed by which the residents of Dorćol, Belgrade's neighborhood which leans on the fortress complex, claimed that the remains of one of those tree churches can still be observed from the river level.

Allegedly, the remains are right under the northern outer bailey, in the central section of the slope between the Defterdar Gate and Nebojša Tower.

When the Ottomans conquered the city that year, the remains were transferred to Iași in Moldavia (modern Romania) and the church was demolished.

The cult of Saint Petka as the healer was so strong, that members of all confessions (Orthodox, Catholics, Muslims), pilgrimaged the spring named after her in the fortress, which was believed to heal the blindness.

It was part of the 1723-1739 Baroque reconstruction of the fortress, and the entire city outside the ramparts, conducted by Nicolas Doxat [de].

[1][4] Though obliged by the treaty to demolish everything that was built within the fortress during their occupation, the Austrians didn't destroy the magazine which remained as one of the rare object that survived.

[7] During his first reign, prince Miloš Obrenović referred to the church in his correspondence with the Belgrade's Yusuf Pasha.

The location was strongly embedded into the collective folk remembrance at the time, due to its alleged ancient origins and miraculous spring of Saint Petka.

[4][7] The church was heavily damaged during World War I and suffered constant bombardment of the fortress by the Austro-Hungarian forces from across the Sava.

In October 1915, a grenade fired from the 42 cm Gamma Mörser hit the fortress wall right above the church but didn't explode.

Church was badly damaged by this time and if the grenade exploded (cartridge weighted 900 kg (2,000 lb) and contained 96 kg (212 lb) of TNT), it would destroy the wall of the Zindan Gate tower which was hit and would level the church to the ground as it is located below the wall.

They were all made of melted military materials: rifle and pistol bullets, shell cases and sabres.

[6] Krasnov especially designed the side portal where these statues are placed, so as the bronze icon of the Mother of God.

Newspapers reported about the event on daily basis, and when the grenade was taken out, it was publicly announced that the fortress is safe for the visitors.

[6] It was during this works that an ossuary of the World War I defenders of Belgrade was built within the lower walls of the Jakšić Tower, right next to the religious complex.

Collaborationist administration invited priests and adherents to continue using the church, and to "keep it alive", but the residents refused.

[4] Only after World War II, with the new Communist government, Ružica stopped being military and garrison church, and worship services began to be conducted by the monastics and priests of the Patriarchate and the Eparchy of Belgrade-Karlovci.

[4] Serbian Orthodox Church set an unofficial rule that the services and sermons in the Ružica were held by the professors from the Belgrade's Saint Sava Seminary.

During the rigid Communist period after World War II, a local raion committee fired the headmistress of a kindergarten at the corner of the Dušanova and Tadeuša Košćuška streets, right across the park, and issued monetary fines to the teachers, cause they organized children to visit the church.

[6] Momčilović painted the icons on the iconostasis using technique oil on plywood, after the sketches of bishop Irinej Đurić.

Todorović carved the bulkheads of the iconostasis in the shallow, gold plated wood engraving to recreate the medieval Serbian Morava style.

Western section represents Jesus Christ's Sermon on the Mount, with priest Petar Trbojević and King Alexander in the audience.