Inicialmente, la parroquia de Leóncio en Yaroslavl se encontraba en la Ciudad de Tierra, cerca del monasterio de Kirilo-Afanásievsky. En 1635, en el lugar de la antigua iglesia de madera, se construyó una nueva iglesia de piedra, dedicada al santo Leóncio, obispo y milagroso de Rostov, con una capilla de los Nueve Mártires de Cizicos y un campanario sobre la entrada. El comerciante de Rostov, Vasili Fedotov Malgin, hizo una contribución significativa a la construcción. En 1688, los feligreses levantaron en el lugar de la quemada iglesia de madera una segunda iglesia de piedra, de cinco cúpulas, la iglesia de la Natividad de Cristo, así como un edificio de piedra para un asilo. Entre los constructores del templo destaca el nombre del feligrés de la iglesia de Leóncio, el comerciante de Yaroslavl, Iván Ivanovich Myakushkin, conocido por su caridad. A principios del siglo XVIII, la parroquia contaba con 61 casas, y el número total de feligreses, junto con los que vivían en el asilo, era de aproximadamente 200 personas.

En 1778, la emperatriz Catalina II aprobó un plan general para la nueva construcción regular de Yaroslavl, que cambió significativamente la antigua y caótica planificación de la parte central de la ciudad. Según este plan, el terreno donde se encontraban las iglesias de la parroquia de Leóncio fue destinado para la construcción de nuevos edificios estatales. Por lo tanto, en 1783 se decidió disolver la parroquia en la Ciudad de Tierra, y los edificios de la iglesia fueron desmantelados y reconstruidos en el nuevo cementerio de la ciudad en el camino a Uglich. El edificio consistía en un comedor cálido con dos habitaciones laterales para las capillas, el templo principal, el altar y un campanario de 8 sazhen. La consagración de la nueva iglesia tuvo lugar el 23 de mayo de 1791, en el día de la adquisición de las reliquias del santo Leóncio de Rostov. La iglesia no tenía parroquia.

La pintura mural fue realizada, como decía la inscripción del templo, en 1806 y 1809 por el contratista Semen Stepanov Zavyazoshnikov y sus aprendices Jarlampy Petrov Dryanin y Vasili Petrov. La decoración incluía 107 escenas en el comedor, el altar y las capillas. En 1834 y 1888, los frescos fueron renovados. El iconostasio fue realizado en la década de 1830 por el tallador de la localidad de Bolshie Soli (actualmente el asentamiento de Nekrasovskoye) Vladimir Trubnikov.

En 1894, se abrió una escuela de alfabetización para niños de las aldeas cercanas y de los suburbios occidentales de la ciudad en la iglesia de Leóncio. También existía un asilo público en la iglesia, cuyo edificio de dos pisos fue construido con donaciones voluntarias en 1846 y 1847 y se ha conservado hasta nuestros días.

En 1931, la iglesia de Leóncio fue entregada a una comunidad religiosa de orientación renovadora. Sin embargo, debido a su escaso número, la comunidad no pudo cubrir todos los gastos de mantenimiento del edificio, y el 7 de diciembre de 1940, el comité ejecutivo del Consejo de la Ciudad de Yaroslavl disolvió la comunidad. Durante la época soviética, el interior de la iglesia fue modificado (se añadió un segundo piso), y la pintura mural se perdió prácticamente, excepto por pequeños fragmentos en la parte del altar.

En 1991, la iglesia del cementerio de Leóncio fue devuelta a la Iglesia Ortodoxa Rusa, se realizaron reparaciones y se reanudaron los entierros en el cementerio de Leóncio.