L'église de la Sainte Grande Martyre Catherine, également connue sous le nom d'église Sainte-Catherine, est située à Théodosie, en face de la gare ferroviaire "Aivazovska", anciennement appelée "Sarygol", près de la gare routière. Ce temple attire l'attention par son architecture vive et ornée.

Le 21 avril 1892, le jour de la naissance de l'impératrice Catherine II, la pose de la première pierre de l'église en l'honneur de Sainte Catherine a eu lieu, afin de commémorer l'annexion de la Crimée à la Russie sous le règne de Catherine la Grande.

La construction de l'église a été financée par les habitants de Théodosie : le procureur général du Saint-Synode a fait un don de 3000 roubles, et le docteur en sciences mathématiques V.I. Lapchine a également contribué de manière significative. Les commerçants de la ville ont fourni les matériaux de construction, et les ouvriers ont travaillé gratuitement les dimanches. Le comité de construction était composé de citoyens respectés : le maire de la ville Altoukhov, le recteur de la cathédrale Alexandre-Nevski Ivanitski et l'ingénieur constructeur de la ligne de chemin de fer de Théodosie Mejeninov. Le comité était dirigé par V.K. Vinogradov, directeur du gymnase masculin de Théodosie.

L'église était rattachée à la cathédrale Alexandre-Nevski. Cela est mentionné dans l'article "La ville et le nouveau temple ont été ressuscités", publié dans le journal "Bulletin gouvernemental" n° 132 de 1892 : "Puisque la cathédrale de la ville est dédiée à Saint Alexandre Nevsky, l'église qui lui est rattachée est supposée être dédiée à la Sainte Grande Martyre Catherine, en mémoire également de l'annexion, sous le règne de l'impératrice Catherine la Grande, de la péninsule de Tauride à l'État russe. Le 21 avril dernier, le jour de la naissance de l'impératrice Catherine II, avec la bénédiction de l'illustre Tikhon de Tauride, la cérémonie de pose de la nouvelle église au nom de Sainte Catherine a été réalisée en face de la gare ferroviaire de Théodosie. Avec une immense foule de presque tous les habitants de Théodosie, une procession a eu lieu de la cathédrale jusqu'au site de construction du temple."

L'église Sainte Catherine est un exemple frappant de l'architecture cultuelle russe, construite dans les traditions architecturales du XVIIe siècle. Sa base est un plan en forme de croix grecque, les murs sur un haut socle sont séparés par des colonnes. L'entrée, encadrée par un portique, est située du côté ouest, au-dessus de laquelle se dresse un clocher orné de colonnes. Le tambour lumineux est une pyramide avec un petit dôme doré. De chaque côté du tambour, il y a quatre grandes fenêtres en arc avec des motifs sculptés. La lumière pénètre dans le temple également par des fenêtres rectangulaires dans les murs. Le sommet du bâtiment est décoré d'un système de kokoshniks, et le dôme est composé de cinq petits dômes peints en bleu et ornés d'étoiles.

L'histoire de l'église Sainte Catherine est étroitement liée à la vie et à la mort du prêtre Andreï Kosovski, qui en était le recteur depuis 1901. Après que la Crimée soit passée sous le contrôle des rouges en 1920, le père Andreï a été arrêté directement dans le temple pendant le service, coïncidant avec la fête patronale. Il a passé de longs mois en détention et a été exécuté sur ordre de la commission d'enquête de la Tchéka. En 2000, la commission synodale pour la canonisation des nouveaux martyrs l'a élevé au rang de saint, et dans les prières, il est mentionné comme Andreï de Théodosie.

En 1937, l'église a été fermée et transformée en entrepôt, mais en 1941, elle a été rouverte par les autorités d'occupation allemandes. Depuis lors, elle reste l'une des rares églises en activité en Crimée.

En 1999, un temple dédié à Saint Jean-Baptiste a été ajouté à l'église Sainte Catherine, avec un baptistère et des locaux pour l'école du dimanche. En 2002, des travaux de rénovation majeurs ont commencé sur l'église, qui ont évolué en la construction d'autres installations. Un complexe a été créé, comprenant des locaux pour l'école du dimanche, un bureau méthodologique, une bibliothèque et un hôtel.