Первая церковь на этом месте была основана в конце XVI века московскими стрельцами и пушкарями, прибывшими для охраны Уфимского кремля и его жителей. Храм был посвящен преподобному Сергию Радонежскому, которого особо почитали защитники города. В 1774 году эта деревянная церковь сгорела во время восстания под предводительством Емельяна Пугачева. В 1777 году на ее месте была построена новая деревянная церковь, прослужившая до 1860-х годов.
В 1868 году, на месте прежней, была возведена новая деревянная церковь на каменном фундаменте. Строительство осуществлялось под руководством настоятеля храма протоиерея Федора Троицкого, который внес значительный вклад в украшение церкви, написав для нее множество икон и позолотив иконостас и киоты. В 1894 году на средства уфимского купца Федора Чижова был установлен новый иконостас, выполненный резчиком Трапезниковым. Известный русский художник Михаил Нестеров, уроженец Уфы, написал для храма два холста с изображением сцен из жития преподобного Сергия Радонежского.
В 1933 году, после закрытия других крупных храмов города, Сергиевская церковь получила статус кафедрального собора. Примечательно, что этот храм не прекращал свою деятельность даже в советский период, оставаясь единственной действующей церковью в Башкирии на рубеже 1930-х и 1940-х годов. В 1942 году в храме возобновились регулярные богослужения. В 1945 году, за активное участие прихода в сборе средств на нужды обороны, собор получил благодарность от Главнокомандующего.
Архитектурно собор представляет собой деревянное здание, обшитое тесом, с двусветным четвериком, увенчанным пятиглавием. К основному объему примыкают трапезная и трехъярусная колокольня. В интерьере храма сохранился резной иконостас работы Трапезникова, а также иконы, написанные Михаилом Нестеровым.
