Первые упоминания о православной жизни в селе Новосысоевка относятся к концу XIX века. В 1898 году началось строительство каменного Успенского храма в форме базилики, которое из-за нехватки средств завершилось лишь в 1904 году. Одновременно была освящена часовня при церкви. В 1927 году храм был закрыт, а его имущество разграблено. В последующие десятилетия здание использовалось для светских нужд: с 1930 по 1961 год здесь размещались различные организации, затем аэроклуб, Дом культуры профтехобразования и Дом Союза композиторов.
Возрождение приходской жизни началось в конце XX века. 25 октября 1999 года община прошла государственную регистрацию. В январе 2000 года освятили молельный дом в переданном епархии жилом здании. Около 2002 года началась публикация приходской газеты «Дорога к храму». В 2006 году заложили фундамент нового храма, строительство которого завершилось в 2011-2012 годах. 28 сентября 2012 года на церковь установили купола.
Прежний молельный дом после перерыва был переосвящен как храм во имя преподобного Сергия Радонежского и стал частью местного женского скита. 31 января 2016 года состоялось освящение семи колоколов, пожертвованных храму. Архитектурно здание представляет собой малый деревянный храм с синим куполом и шатровой колокольней.