Строительство храма в честь святого великомученика и Победоносца Георгия в городе Орске было начато в конце XX века. В 1999 году администрация города выделила участок земли в парке воинов-интернационалистов, расположенном в микрорайоне Новый город. Выбор святого Георгия в качестве небесного покровителя храма обусловлен его расположением на территории парка, посвященного воинам, так как святой Георгий традиционно почитается как покровитель военнослужащих.
Первоначально на этом месте была возведена деревянная церковь, освященная в 2001 году. Храм быстро стал популярным среди верующих, и уже через год к нему был пристроен придел в честь святой блаженной Ксении Петербургской. Однако вскоре и это здание перестало вмещать всех молящихся, что привело к необходимости строительства более вместительного каменного собора.
Закладка каменного собора состоялась в 2008 году. Проект храма был выполнен архитектором Юрием Алексеевичем Григорьевым в стиле русского модерна с тринадцатью шлемовидными куполами. Строительство велось на пожертвования прихожан, среди которых особо отмечается вклад орского пенсионера Ивана Григорьевича Досковского, передавшего на строительство один миллион рублей.
6 сентября 2014 года состоялось великое освящение кафедрального собора, которое совершил митрополит Оренбургский и Саракташский Валентин. Собор имеет два престола: верхний освящен в честь святого великомученика Георгия Победоносца, а нижний — в честь святой блаженной Ксении Петербургской. Храм является двухуровневым, что позволяет проводить богослужения одновременно в обоих приделах.
В 2011 году была образована Орская епархия, и храм получил статус кафедрального собора. С этого времени он стал центром духовной жизни не только города Орска, но и всей епархии. При соборе действует иконописная мастерская, а также проводятся различные социальные и образовательные мероприятия.