Великокняжеская церковь появилась благодаря почетному гражданину Ельца, купцу и промышленнику Александру Заусайлову. Его трудами и заботами город украшен во многих местах, но Великокняжеская церковь и Дом призрения превзошли все остальное. В 1883 году на Успенской улице по проекту Александра Каминского была возведена Царская часовня в память об убитом народовольцами царе-освободителе Александре II, ставшая впоследствии своеобразным притвором храма.

Мысль о сооружении церкви во имя святых благоверных князей Михаила Тверского и Александра Невского зародилась у Заусайлова в связи с посещением Ельца 2 октября 1909 года братом царя Николая II Михаилом Александровичем Романовым. Россия готовилась отметить 50-летие манифеста 1861 года его деда Александра II об освобождении крестьян. Проект церкви талантливо разработал орловский архитектор Вильфорд. Строительство было произведено в удивительно короткий срок — за год и три месяца. Работы по возведению храма не прерывались даже в холодное время года: над местом стройки возвели огромный отапливаемый шатер. Также были использованы все технические новинки начала XX века: бетонные своды, электричество, автоматически убираемые сидения, водяное отопление, водопровод. С севера и запада входы в храм украсили ажурные чугунные крыльца-сени на фигурных столбах. Котельная размещалась под соседним зданием, а в подвале были смонтированы радиаторы, нагревавшие воздух, который по каналам в стенах поднимался в храм.

12 марта 1910 года состоялось торжественное водружение креста. Полый внутри «хрустальный» крест был выполнен на металлическом каркасе, сверкал на солнце, а ночью подсвечивался электричеством. По верху главного купола проложили медную трубку с отверстиями и фонтанчики воды в летнее время омывали крест. Купола храма были вызолочены, кровля покрыта медью. Чердачное помещение отапливалось. 18 августа 1910 года на звонницу был поднят главный колокол весом в 100 пудов. Задуманное архитектором Вильфордом роскошное, насыщенное деталями убранство фасада при строительстве было несколько упрощено, но всё же производит впечатление богатства и праздничности во многом благодаря применению полихромных изразцов с текстом молитвы и травными орнаментами.

Ещё большее впечатление оставляет внутреннее убранство храма, стены и своды которого полностью покрыты майоликовой плиткой, имитирующей мозаику. Иконостас был также выполнен из майолики. Царские Врата были серебряными, а иконы выполнены в технике масляной живописи. Вместе с цветными витражами интерьер, особенно в ночное время, когда зажжены свечи в храме, мерцает и переливается огнями сказочной красоты. Пол был паркетный, а панели стен отделаны дубовой рейкой. Освящение храма состоялось 11 февраля 1911 года. Прихожанами являлись члены общества хоругвеносцев. К 300-летию династии Романовых, всего за год, с 1912 по 1913, Заусайлов рядом с церковью построил Дом Призрения — приют для сирых и убогих, выполненный по проекту известного живописца и монументалиста Виктора Васнецова.