The Church of Gregory the Theologian was built in the 1670s on the territory of the Metropolitan Garden. Previously, in the 16th century, there were the chambers of the Grigoryevsky Monastery, which was abolished in the 17th century during the construction of the new Archiepiscopal Court. The new church was erected on the old foundation and harmoniously blended into the panorama of the Rostov Kremlin.

The original decoration of the church was lost as a result of the fire in 1730. It is unknown whether the Church of Gregory the Theologian existed in the 17th century. Like other churches of the Rostov Archiepiscopal House, it was adorned with fresco paintings.

In the 1740s, under Archbishop Arsenius, the interior of the temple was decorated with stucco and ceiling glue painting. The greenish walls inside are divided by fluted pilasters, between which there is stucco with floral motifs, cartouches, and shells. These forms are executed with decorative taste and temperament, revealing the hand of a master from the common people.

The cartouches depict gospel scenes: on the western wall, the Pre-Pascha, the Annunciation, the Conversation with Nicodemus; on the southern wall, the Entry into Jerusalem; on the northern wall, the Nativity of the Mother of God; in the drum, the Fatherland; in the altar, the Last Supper, Sabaoth, the Agony in the Garden.

In 1884, the interior of the church was updated in the Russian style by the artel of N.M. Safonov. The restoration was funded by peasant I.A. Rublev under the supervision of the Moscow Archaeological Society. During the restoration, the paintings in the cartouches were changed. On the western wall, new images appeared: the Sermon on the Mount, the Expulsion of the Merchants from the Temple, the Feeding of the Five Thousand with Five Loaves. On the eastern wall, there is an image of Anthony the Roman, sailing on a stone from Rome to Novgorod. The window slopes are decorated with a grass ornament in the Russian style, consisting of green and red shoots on a yellow background. The grass pattern covers the walls and vaults of the temple, the porches, and the narthex. The windows were fitted with patterned frames with multicolored glass.

In the 1880s, a new iconostasis was installed in the church, decorated with gilded carvings on a red background. The royal gates for the iconostasis were made by the Rostov carver Nikolsky based on the royal gates of the Theological Church on the Isha River. These gates were transferred to the Isha Church, while the unique gates from the Church of John the Theologian, carved in 1562 by monk Isaiah, are now on display at the Rostov Museum.

All the icons of the five-tiered iconostasis were created in the 1880s by the masters of the Safonov artel, including local craftsmen. Among them are the Mother of God with Saints Anthony and Theodosius, the Almighty with the Gospel, Stephen of Perm in his life, Gregory the Theologian, Blessed Elizabeth, the Conception of John the Baptist.