Дворцовый комплекс Сейд-Худояр-Хана в Коканде построен в 1871-1873 годах по проекту Мира Убайдулло.
19 февраля 1876 года Коканд был занят российскими войсками под началом генерала М.Д. Скобелева. Ханство упразднено, и Коканд вошёл в образованную Ферганскую область в составе Туркестанского генерал-губернаторства Российской империи, став административным центром Кокандского уезда. После присоединения Коканда к России ханский дворец был превращен в крепость, а тронный зал ханского дворца был переоборудован под церковь. Для её обустройства были приглашены лучшие резчик и мастера по иконостасному делу. По указу Туркестанской Духовной Консистории за № 255 от 12 сентября 1876 года церковь во дворце 23 декабря 1876 года была освящена в честь Святых Равноапостольных Константина и Елены священником Победоносцевым. Она вмещала 100 человек молящихся.
До 1900 года храм и причт состояли в ведении Туркестанского Епархиального Начальства. Она именовалась «церковью при Управлении Кокандского воинского начальника», с 1912 — «военно-местною», с 1922 — храм Святых Равноапостольных Константина и Елены. Церковь действовала до 1929 года, когда была упразднена.