В Бирске, столице уезда, было решено для просвещения инородцев построить храм, в котором помимо богослужений на церковно-славянском, некоторые фрагменты проходили бы на черемисском, марийском и татарском языках. В 1894 году учрежден строительный комитет и начат сбор пожертвований. Первыми жертвователями стали бирские купцы Н.С. Капустин и С.М. Белов. Среди инициаторов строительства церкви выступали инспектор школы Николай Павлович Вешневский и законоучитель священник Александр Федорович Михайлов. Храм заложен летом 1895 года. Дело продвигалось довольно споро, и к осени 1898 года строительные работы были завершены. Для церкви был изготовлен оригинальный крест, состоящий из граненых стеклянных квадратиков, вставленных в золоченую оправу; 6 сентября 1898 года он был поднят на главный купол. Освящение храма состоялось 4 апреля 1899 года во имя Казанских святителей XVI века Гурия, Варсонофия и Германа, известных как просветителей инородцев бывшего Казанского ханства. Поэтому вскоре после постройки и по сей день широко бытует второе название церкви – «инородческая», хотя в чистом виде она никогда таковой не была. Хотя храм появился во дворе Бирской инородческой учительской школы, он был рассчитан на посещение его воспитанниками всех учебных заведений города.
Храм расположился на южной стороне внешнего периметра Соборной площади в сотне метров от Троицкого собора. Это единственный в Башкирии памятник, наиболее последовательно ориентированный на воспроизведение средневековой византийской традиции. Центрическая крестово-купольная композиция обнаруживает, при ближайшем рассмотрении, элементы базиликальности. Расположенный над средокрестием восьмигранный барабан завершен куполом. Рукава креста покрыты в два ската; угловые части, дополняющие план до компактного прямоугольника – в один. К квадратному храму примыкает с западной стороны почти равный ему по ширине короткий нартекс, а с восточной сравнительно узкая, но более выдвинутая алтарная апсида. Постепенное нарастание высоты объемов к центру удачно обыграно силуэтами скатных кровель. Их графичные ломано-линейные очертания подводят взор к купольному венчанию, в котором преобладают лекальные и полуциркульные составляющие. С трех сторон, кроме восточной, в здании имеются входы, расположенные по оси ризалитов. На северном и южном фасаде над ними помещается аркада из трех окон, среднее из которых заметно приподнято по отношению к боковым. Первоначально, неоштукатуренные снаружи стены были покрыты розовым колером, угловые лопатки и карнизы побелены. Ныне церковь утратила эту отделку, что роднит ее облик с постройками в так называемом кирпичном стиле. Особенно выразительны четко очерченные горизонтали ленточной рустовки, проходящие по всем фасадам. Шесть крещатых столпов делят внутреннее пространство церкви на три нефа. Отопление церкви было устроено по последнему слову техники: духовая печь, расположенная в подвале, обогревала здание теплым воздухом, циркулирующим в воздушных колодцах внутри церковных стен. Полы выложены брусчаткой и плитами.
С наступлением советского времени церковь была закрыта одной из первых в уезде. Снесена небольшая кирпичная надвратная звонница, стоявшая отдельно от храма несимметрично к северо-западу от него. Здание было отдано под комсомольский клуб, ресторан, некоторое время здесь был музей, потом разместили склады, в послевоенные годы в нем была даже электростанция. С 1984-1985 годов начинается реставрация церкви с приспособлением под краеведческий музей, но этому не суждено было сбыться – и в 2004 году музей размещается рядом в деревянном здании бывшей инородческой школы. Около 1994 года храм возвращен Уфимской епархии. В 2002 году построена новая кирпичная звонница, она встала несколько восточнее места снесённой, так как по фундаменту старой прошла теплотрасса. 17 января 2003 года на звонницу был установлен крест. В начале 2002 года стараниями настоятеля о. Дионисия Долженко при церкви начала действовать воскресная школа.
