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.