The plan "Kremlenagrad" from the early 1600s shows a small church with a single dome rising above a number of ogee arches, and two side chapels to the east of the bell tower of Ivan the Great and the Church of the Nativity in Ivanovskaya Square. It is the Cathedral of Chernigov Wonderworkers Prince Mikhail and his Boyar Fyodor, who were martyred by the Horde for not following pagan rites. The exact date of its construction is unknown. The church was built in the Kremlin after Ivan the Terrible decided to transfer the relics of the Great Martyrs from Chernigov to Moscow. A letter of the Tsar to the deceased saints has been preserved. He addressed them as if they were alive, asking to receive their relics, but not as relics, but as "... you yourselves will come to us and enlighten us and save the city, will you, by God's will, live with us in the reigning city of Moscow...". According to the time of the Metropolitan Anthony's tenure in Moscow, to whom Ivan the Terrible refers in his Letter to the Saints, this event, and thus the construction of the cathedral, took place in the 1570s.

Cathedral of the Chernigov Wonderworkers  on the “Kremlenagrad” plan, fragmentPrint “View on the Moscow Kremlin from Zamoskvorechye District at early 18th century”

The Church of the Wonderworkers of Chernigov was probably originally called a cathedral. The naves of the northern and southern façades were dedicated to the renewal of the Church of the Resurrection and to St Nicholas the Wonderworker. According to the picture on the drawing "Kremlenagrad", the façades of the cathedral had a tripartite section and were surmounted by multifarious arched gables above which there was a row of ogee arches enclosing the dome. There were three lowered apses to the east. Ogee arches are also depicted above the naves below the domes. As a whole, the building gives an impression of elegance and cosiness.

By the end of the 1670s the church had apparently fallen into disrepair, for in 1681 the relics of the Chernigov wonderworkers were being conserved in the Archangel Cathedral, where their feast day was celebrated then.

In 1681-1683, during the construction of the new Prikaz Chambers (state office) on Ivanovskaya Square in the 1675-1680s, instead of the previously planned Church of the Three Confessors next to the gate leading to the Tainitskaya Tower, two churches were built under one roof. The altars of the Chernigov wonderworkers and of St Prince Alexander Nevsky were moved here. The latter was in the church built under Patriarch Philaret in 1630 on the eastern side of the bell tower near the Church of the Chernigov Wonderworkers. The old, obviously dilapidated buildings were demolished. Both churches were consecrated in 1683 and the relics of the saints were transferred from the Archangel Cathedral to the newly built Church of the Wonderworkers. Tsar Peter I attended the ceremony.

An early 18th-century engraving illustrating a view of the Kremlin from Zamoskvorechye district also shows these churches. They were located to the west of the gates, which were called Verhniye Tainitskiye, and after the churches were built, the gates were also called Chernigov’s. The churches, similar in architecture, stood one after another in a north-south direction above the first level of the Prikaz Chambers. Ten domes surmounted a one-piece four-slope roof. The buildings were surrounded by the open gallery to which a staircase led from Ivanovskaya Square.

In 1772, during the preparations for the construction of the Kremlin Palace according to the project of V. Bazhenov, both churches were demolished along with the whole building of the Prikaz Chambers.