Первая соборная мечеть была построена в 1830 году по ходатайству муфтия Оренбургского магометанского духовного собрания Габдессаляма Габдрахимова на средства купца 2-й гильдии г. Уфы Мукмина Хозясеитова. К началу XX века в приходе насчитывалось 920 человек. При мечети действовало медресе «Гусмания» и русско-башкирское 2-классное училище. В 1960—1992 гг. Первая соборная мечеть являлась единственной действующей мечетью в городе Уфе.
Известные имам-хатыбы: Г. Габдрахимов (с 1830 года), А. Габдуссалямов (с 1840 года), Ш. Г. Сулейманов (1844—1885), Гусманов (с 1888 года), Д. Т. Абзгильдин(1907—1938), Б. В. Тугузбаев, Н. М. Нигматуллин (1983—1992), М. М. Мухамадисламов (1992—2006), В. М. Тимиргалиев (с 2006 года).
В 1989 году на основании Постановления Совета по делам религий Кабинета Министров СССР на базе мечети было открыто Медресе имени Ризаитдина Фахретдина. Здание мечети является объектом культурного наследия.
В народе мечеть называется Тукаевская мечеть. Существует две версии такого наименования. Одна версия утверждает, что мечеть названа в честь известного башкирского рода религиозных деятелей Тукаевых из Стерлибашево. В XIX веке Стерлибашевское медресе было центром мусульманской науки в России. Другая версия говорит, что мечеть названа именем улицы, на которой она находится.