1574 wurde Ufa als Festung gegründet. Damit sollte nach dem Anschluss der Baschkirischen Gebiete die Südostgrenze Russlands gesichert werden. Aus historischen Dokumenten geht hervor, dass nach der Unterwerfung des Kasaner Khanates Botschafter im Namen Iwans IV. in dieses Gebiet gesandt wurden, um ihnen den Beitritt zur russischen Obrigkeit nahezulegen. Im Zeitraum von 1554-1557 erfolgte der freiwillige Beitritt aller baschkirischen Stämme in den Staatenbund Russlands. Da sie jedoch weiterhin von Überfällen kriegerischer Nomaden geplagt wurden und es im gesamten Gebiet keine Städte oder militärischen Anlagen gab, wurde 1574 an der Mündung des Flusses Ufa in die Belaja nahe der alten Kasaner Handelsstraße eine kleine Befestigung aus Eichenholz durch eine Division des russischen Schützenkorps errichtet - die Festung Ufa. Zu dieser Zeit gab es nicht eine einzige Stadt im heutigen Russland, die östlicher davon gelegen hätte - bis hin zum Stillen Ozean. Ein 440m langer Eichenholzwall umgab die kleine Festung, von daher stammt auch ihr damaliger Spitzname, die „Eichenstadt“. Im Jahr 1586 wurde Ufa das Stadtrecht verliehen.
Im Jahr 1635 wurde die Stadt durch Truppen der sibirischen Fürsten Tjawka und Ablai belagert, welche aber in die Flucht geschlagen werden konnten. Am 23. Mai 1759 wurde in der Stadt durch Blitzschlag ein Feuer ausgelöst, das die Holzfestung und weite Teile der Stadt zerstörte. Zugleich wandelte sich die Stadt im 17. und 18. Jahrhundert schrittweise von einer militärischen Festung in das politische und wirtschaftliche Zentrum der Region. Politisch gehörte die Stadt ab 1708 zum Kasaner Gouvernement. Ab 1728 war Ufa Hauptstadt der Ufaer Provinz, die unmittelbar dem Senat unterlag. Von 1744 gehörte zum Gouvernement von Orenburg. Seit 1772 beherbergte das Rathaus den Stadtrat zur Selbstverwaltung der Stadt. Elf Jahre später, im Dezember 1781 wurde Ufa Hauptstadt der neuen Ufaer Provinz, bevor es 1796 wiederum zum Orenburger Gouvernement kam. Seit 1802 war Ufa Gouvernementsstadt mit zeitweiliger Residenz des Gouverneurs und seiner Verwaltungseinrichtungen. Im Jahr 1865 wurde Ufa per Dekret des Zaren Alexander II. zur Hauptstadt des Gouvernements Baschkirien erhoben. Im 19. Jahrhundert begann die Industrialisierung Ufas. Mitte des 19. Jahrhunderts existierten bereits etwa ein Dutzend Gerberbetriebe und einige Anlegestellen am Fluss. Bedeutend für die weitere Entwicklung waren die Einführung der regulären Schifffahrt auf der Belaja 1870 und die Eröffnung der Kasan-Zlatouster Eisenbahn 1888-1892. In der Stadt entstanden Dampfmühlen, Sägewerke, Eisenbahn- und Schiffsreparaturwerkstätten. Ende des 19. Jahrhunderts zählte Ufa ca. 30 Fabriken - lebensmittel-, leder-, silikat- und holzverarbeitende Betriebe. Zudem wurde Ufa ein bedeutender Ort im Fleisch- und Teigwarenhandel.
Hauptstadt war Ufa auch für die Baschkirische Autonome Sozialistischen Sowjetrepublik BASSR (seit 1922). In den folgenden Jahren wurde im Zuge des ersten Fünfjahresplans eine Motorenfabrik und die erste TEZ (Fernelektrititätswerk) gebaut, und 1939 wird der erste erdölverarbeitende Betrieb Ufas eröffnet. In den Zwanzigern und Dreißigern des 20. Jahrhunderts entwickelte sich die Stadt weiter. Die industrielle Produktion stieg in diesem Zeitraum auf das 16fache. Das Ufaer Industriekombinat, bestehend aus einer Streichholz- und einer Glühbirnenfabrik, einem Sägewerk und einer Großgerberei, wurde gebaut. Hinzu kamen weitere Betriebe im Bereich der Lebensmittel- und der leichten Industrie. Während des Zweiten Weltkrieges wurden etwa ein Dutzend industrieller Großbetriebe, viele Behörden und eine Reihe von wissenschaftlichen Instituten nach Ufa evakuiert, so auch auf Anordnung Stalins die Kommunistische Internationale (Komintern).
In der Nachkriegszeit spielte die Ausbeutung und Verarbeitung der Erdölvorkommen Baschkiriens die größte Rolle in der Ufaer Wirtschaft. Die "Neu-Ufaer Ölverarbeitung" wurde in den Fünfziger Jahren eröffnet. Der dritte erdölverarbeitende Betrieb folgte bald darauf. Daneben fassten auch die chemische und die Maschinenbauindustrie in der Stadt Fuß. Auf Beschluss des Sowjet der BASSR wurde der Stadt Ufa am 24. Juli 1956 die Stadt Tschernikowsk im Norden Ufas als Stadtteil Ordschonikidse eingegliedert.
Seit 1991 ist Ufa Hauptstadt der damals entstandenen Republik Baschkortostan. Internationale Bekanntheit erlangte die Stadt, als 2002 bei der Kollision einer Tupolev-154 der Bashikirian Airlines und einer Boeing über dem Bodensee bei Überlingen am 1. Juli vor allem aus Ufa stammende Passagiere, darunter 52 Schulkinder, starben.