Dibināta kā Krievijas caristes cietoksnis 1574. gadā Nogaju ordas nocietinājuma Turatau vietā pēc tam, kad tās karaspēks bija ieņēmis Kazaņu.
Pilsētas tiesības tā ieguva 1586. gadā. No 1802. gada bija guberņas centrs, no 1922. gada — Baškīrijas APSR galvaspilsēta.
Otrā pasaules kara laikā uz Ufu pārcēla daudzus uzņēmumus no PSRS rietumu daļas. No 1991. gada — Baškortostānas galvaspilsēta.
Sports
Jau kopš 1957. gada pilsētā ir bāzēta viena no spēcīgākajām Krievijas hokeja komandām Ufas "Salavat Julajev". Tā spēlē KHL un ir 2008., kā arī 2011. gada Krievijas čempione. Jaunatnes hokeja līgā spēlē arī "Salavat Julajev" jauniešu klubs Ufas "Tolpar".