La stanitsa de Novodonetskaya fue fundada en 1833 en el lugar de un asentamiento campesino, donde vivían 240 personas. La primera iglesia de la stanitsa, construida en la primera mitad del siglo XIX, se quemó. En 1856, en su lugar se construyó una iglesia de madera de la Santísima Trinidad sobre un cimiento de piedra. Las dimensiones de la iglesia eran: longitud con el campanario, 23,1 metros; ancho, 12,8 metros; altura hasta el alero, 6,4 metros. Con el tiempo, el edificio se deterioró mucho, lo que requirió la construcción de un nuevo templo. En 1911 se colocó la primera piedra de la iglesia de piedra, cuya construcción se completó en 1914. La solemne consagración del nuevo templo tuvo lugar el 31 de mayo de 1914, oficiada por el obispo de Yeisk, Juan.

No se han encontrado documentos relacionados con el proyecto y el autor de la iglesia de la Santísima Trinidad en los archivos. Se supone que el autor del proyecto fue Alexander Petrovich Kosiakin, quien construyó templos similares en otras stanitsas. En 1916, el número de feligreses era de 5540 personas, de las cuales 4170 eran cosacos con sus familias. En la iglesia se guardaban documentos eclesiásticos, libros y catálogos, así como libros métricos desde 1830, excepto los perdidos en el incendio. La escuela parroquial se ubicaba en un edificio perteneciente a la iglesia, y se asignaban 100 rublos anuales para su mantenimiento.

Para 1916, la iglesia de la Santísima Trinidad de Novodonetskaya no solo era un importante sujeto económico, sino que también desempeñaba un papel clave en la educación y la vida espiritual de la stanitsa. Desde 1872, pertenecía al sexto distrito de supervisión, primero de la diócesis del Cáucaso y luego de la diócesis de Stavropol. En el personal de la iglesia había dos sacerdotes, un diácono y dos salmistas. A la iglesia se le asignaron 264 desiatinas de tierra, bajo la administración de la comunidad, y 165 desiatinas, en uso del clero. En 1916, en la escuela estudiaban 37 niños y 17 niñas, y la maestra era Antonina Ivanovna Svitlova.

Además de la escuela parroquial, en la parroquia funcionaban una escuela ministerial de dos clases, una escuela de un solo grado para mujeres, una escuela mixta de un solo grado oriental y una escuela en el mercado cerca de la estación 'Bursak'. Los servicios en la iglesia continuaron hasta 1933, después de lo cual se remodeló como club. Durante la Gran Guerra Patria, la iglesia volvió a abrir sus puertas el 15 de noviembre de 1942, para mantener la espiritualidad del pueblo. En 1964, la iglesia fue cerrada, y en 1975 fue incluida en la lista de monumentos arquitectónicos de importancia local. En 1978, el edificio fue transferido a la administración cultural regional y se utilizó como almacén de fertilizantes químicos, lo que provocó daños significativos.

En 1990 se formó la parroquia de la iglesia de la Santísima Trinidad, siendo el padre Andrian su rector. En la iglesia medio destruida se instalaron ventanas, y los servicios se llevaron a cabo en su parte delantera. Desde 1991 hasta 2000, el rector fue el padre Sergey Kuryanov, quien comenzó la restauración de las cúpulas. Desde 2001, el rector es el sacerdote Boris Kekejev, quien inició la restauración completa de la iglesia. A principios de la década de 2000, se creó el fondo benéfico 'Renacimiento' para la restauración de la iglesia, dirigido por Alexey Nikolaevich Tkachev. Los proyectos de restauración de la iglesia comenzaron a implementarse en 2004 bajo la dirección del nuevo rector, el padre Trofim Shcherbakov.

Desde el 1 de julio de 2007, el rector es el padre Alexander Efimenko. En 2007-2008 se adquirieron utensilios de iglesia, se pintaron íconos de los santos patronos de la familia del principal benefactor de la iglesia, el gobernador de la región de Krasnodar, Alexander Nikolaevich Tkachev. En 2008-2009, la iglesia fue decorada en estilo neobizantino, basándose en el proyecto de la iglesia de Novo-Afon en Abjasia. La pintura fue realizada por artistas de Rusia y otros países, incluyendo Francia e Israel, utilizando escenas del Nuevo Testamento. En 2008-2010 se construyeron la prosfornia, la capilla de agua bendita y el edificio de la escuela dominical.

Actualmente, la iglesia de la Santísima Trinidad de la stanitsa de Novodonetskaya pertenece a la diócesis de Ekaterinodar y Kuban, bajo la supervisión de Ust-Labinsk y Vyselkov. En la iglesia sirve un segundo sacerdote, el padre Alexey Ovdyenko. El coro 'Antigua Rusia', dirigido por Yulia Nazarenko, interpreta cantos. La actividad de la iglesia incluye dirección catequética-misionera, social-educativa, cultural-creativa y deportiva-turística.