В качестве даты основания Уфы приводятся 1574 и 1586 годы - первая принята в Башкирии, вторая – московскими историками. Согласно местным источникам (полулегендарным, ведь они сгорели в пожаре 1759 года) в 1574 году стрельцы воеводы Ивана Нагого прибыли на берег реки Белой Воложки (Белой).
Город стрельцов и дворян
Осенью 1586 года князь Урус писал царю Фёдору Иоанновичу: «…Ты на четырёх местах хочешь городы ставить: на Уфе, да на Увеке, да на Самаре, да на Белой Воложке». Что сие означает, пока никто толком не расшифровал. Дискуссия относительно возраста Уфы – тема не новая, и особенно она обострилась в канун празднования 300-летия города в 1886 году - его, кстати, уфимцы отметили трёхдневными гуляньями. В том же году прошла очередная перепись населения, по данным которой в Уфе проживало 26 976 человек. Жили тогда уфимцы в среднем по 11 человек в домах, по 6 – в квартирах и по двое в комнате.
В 1635–1636 гг. в Уфе проживало с семьями около 100 конных и 200 пеших стрельцов во главе со стрелецким головой и тремя сотниками. В 1647 г. в городе насчитывалось 66 дворов и в них 206 душ мужского пола (сюда не вошли духовенство и более 300 стрельцов – те «писать не дались»).
В XVII–XVIII веках из города-крепости Уфа постепенно превратилась в административный и экономический центр края, а в 1728 г. стала центром Уфимской провинции, воевода которой подчинялся непосредственно Сенату. В 1744 г. Уфа была приписана к Оренбургской губернии.
Сильный пожар 1759 г., возникший от молнии, уничтожил более 200 домов, в т. ч. деревянные стены Уфимского кремля. В 1760 г. в городе построены первые каменные дома - комплекс административных зданий на исторической территории Уфимского Кремля: дом воеводы, рентерея (хранилище городской казны), здание Провинциальной канцелярии.
В середине 70-х годов XVIII в. в Уфе было 9 улиц: Казанская, Московская, Сибирская, Посадская, Ильинская, Усольская, Фроловская, Сергиевская и Будановская. В 1864 г. на долю дворян приходилось уже 19% уфимских дворов. Кроме того, в ХVIII-XIX веках в Уфе проживало большое число ссыльных и опальных дворян - людей образованных и свободномыслящих.
Начало преобразований
С декабря 1781 г. город становится центром Уфимского наместничества, а в 1796 г. вновь передан в Оренбургскую губернию. С 1802 г. Уфа - губернский город с резиденцией губернатора и губернских учреждений. В 40-е годы XIX в. началось благоустройство улиц, для чего был учреждён т.н. «мостовой сбор». Первыми были вымощены Соборная площадь, улицы Соборная, Большая Казанская, Александровская. На центральных улицах были установлены фонари и высажены деревья, которые вскоре объели козы, которых горожане держали в большом количестве.
В 1865 г. Уфа становится центром Уфимской губернии. Тогда же началось и промышленное развитие города, и уже к середине столетия здесь работало более десятка кожевенных заводов и несколько пристаней. На судьбу Уфы большое влияние оказало открытие в 1870 г. регулярного судоходства по реке Белой и строительство Самаро-Златоустовской железной дороги.
В 1922 г. Декретом ВЦИК Уфимская губерния была упразднена, Уфа объявлена столицей Башкирской АССР (до 1922 г. столицей республики был Стерлитамак).