St Nicholas' Church in Tolmachy is located immediately next to the State Tretyakov Gallery and its oldest part dates from 1697. The yellow vestibule and bell tower were built on later in 1834. However it is not the appearance of the church which generates the most interest but what the church holds inside: the revered Our Lady of Vladimir Icon, which is said to have been painted by the Apostle Luke and is believed to have come to Rus as a present to Prince Yuri Dolgoruky. Over the centuries the icon has featured in many significant events in Russian history.

Since 1997 the working church has been part of the State Tretyakov Gallery after a compromise was reached between the Russian Orthodox Church and the State Tretyakov Gallery as to whether the sacred icon should be held in a church or a museum. In addition to the Our Lady of Vladimir Icon, Rublev's Trinity Icon is moved here from the gallery on Pentecost. Entrance to the church is free of charge and is accessible through the main entrance to the gallery.