Дворцовый комплекс Сейд-Худояр-Хана в Коканде построен в 1871-1873 годах по проекту Мира Убайдулло.
19 февраля 1876 года Коканд был занят российскими войсками под началом генерала М.Д. Скобелева. Ханство упразднено, и Коканд вошёл в образованную Ферганскую область в составе Туркестанского генерал-губернаторства Российской империи, став административным центром Кокандского уезда. После присоединения Коканда к России ханский дворец был превращен в крепость, а тронный зал ханского дворца был переоборудован под церковь. Для её обустройства были приглашены лучшие резчик и мастера по иконостасному делу. По указу Туркестанской Духовной Консистории за № 255 от 12 сентября 1876 года церковь во дворце 23 декабря 1876 года была освящена в честь Святых Равноапостольных Константина и Елены священником Победоносцевым. Она вмещала 100 человек молящихся.
До 1900 года храм и причт состояли в ведении Туркестанского Епархиального Начальства. Она именовалась «церковью при Управлении Кокандского воинского начальника», с 1912 — «военно-местною», с 1922 — храм Святых Равноапостольных Константина и Елены. Церковь действовала до 1929 года, когда была упразднена.
Церковь освящена в 1876 г. Описание: Со взятием Коканда по 23 декабря 1876 года русское православное население города собиралось для молитвы в частных помещениях. В то же время, по распоряжению Командующего войсками Ферганской области генерала М. Д. Скобелева, была отведена для церкви одна из лучших зал ханского дворца, служившая ханам для приема послов. По окончании необходимых работ, согласно указа Туркестанской Духовной Консистории от 12 сентября 1876 г. за N 255, временная церковь в Коканде была освящена священником Победоносцевым 23 декабря 1876 г. До 1900 г. церковь состояли в ведении Туркестанского Епархиального Начальства. Первоначально она именовалась церковью при Управлении Кокандского воинского начальника, а с 1912 г. — военно-местною.
Книга «Туркестан. География и история края». 1914 год.
Церковь располагалась в Тронном зале Дворца Сеид-Худояр-Хана, сейчас музей.
Кокандская церковь (свв. Константина и Елены) временно помещается в бывшем ханском дворце, устроена в 1876 г. Штат: священник и 2 церковника, муж. 904, жен. 389. Священник Николай Алексеевич Коблов.
Календарь Туркестанской епархии на 1903 год
Со двора ход в церковь. Она занимает две лучшие залы бывшего дворца, и роскошные лепные потолки этих зал сохранили еще все былые свои восточные украшения. Иконостас и царские двери своею темною отделкою из полированного чинара вполне подошли к темным бархатистым тонам туркменского ковра, какими расписаны внутри лепные ниши потолка, полные необыкновенного вкуса.
Е. Л. Марков. Россия в Средней Азии: Очерки путешествия по Закавказью, Туркмении, Бухаре, Самаркандской, Ташкентской и Ферганской областям, Каспийскому морю и Волге. — СПб., 1901.