Первоначально непосредственную власть и сбор дани осуществлял казанский наместник. Для закрепления своей власти во вновь присоединенном крае, организации управления им и превращения его в плацдарм для проникновения в казахские степи и Сибирь царскому правительству был нужен опорный пункт. В свою очередь башкиры, страдавшие от частых набегов воинственных степняков, нуждались в постоянной вооруженной помощи Русского государства. Такую помощь им мог оказать только гарнизон города-крепости. Башкирам город нужен был и как место уплаты ясака, который до этого они вынуждены были возить в далекую Казань.
В 1574 году отряд русских стрельцов под руководством воеводы Ивана Григорьевича Нагого на высоком правом берегу р.Белой недалеко от устья реки Уфы построил небольшой укрепленный пункт, который располагался исключительно выгодно с оборонной точки зрения. На юге река Белая представляла степняков почти непреодолимую преграду. Протекавшая с севера на юг река Сутолока защищала укрепление с востока. С северо-востока оно оборонялось особым земляным валом, остатки которого сохранялись до конца XIX века.
Основу будущего города первоначально составлял "кремль", заложенный в 1574-1586 годах. Он занимал южную оконечность высокого мыса на правом берегу р.Сутолоки, пр впадении ее в р.Белую. Вид кремля представлял собой ломаный четырехугольник, общая площадь которого не превышала 1,5 гектара, длина его стен составляла примерно 440-450 метров. Стены были сооружены из поставленных вертикально огромных дубовых бревен, поэтому башкиры сначала Уфу называли Имэн кала (Дубовая крепость или Дубовый город). Кроме того в состав укреплений входили три рубленые из дуба башни, две из которых были проезжие, а одна - пешеходная. Обе проездные башни были двухярусными (восьмигранник на восьмиграннике) и завершались высокими шатровыми покрытиями. Северная башня называлась Михайловской, южная - Никольской (Сутолоцкой).
Относительно происхождения названия города Уфы существует несколько гипотез, однако наиболее вероятным кажется именование нового города по имени реки Уфы (вспомним, например, г.Тобольск, основанный в 1587 году на Иртыше близ устья реки Тобол).
Город Уфа, по словам П.И.Рычкова, был окружен великими горами и находился "между восьми великих и глубоких буераков, из которых в одном, кой идет поперек города, течет речка, именуемая Сутолокой". На левом берегу Сутолоки располагались посады, где жили служилые люди.
В 1579 году в Уфе "освящена каменная церковь во имя Смоленской божьей матери". Существование каменной церкви говорит о наличии значительного для того времени населения, составившего церковный приход. В 1586 году Уфа получила статус города. Уфа становится административным центром Башкирии. Управление краем осуществлялось уфимским воеводой, подчиненным казанскому наместнику.
Появление города-крепости в центре Башкирии степными соседями башкир (ногайскими мурзами, сибирским ханом и другими кочевниками) было встречено крайне враждебно. На Уфу совершались неоднократные нападения, но все они успешно отражались гарнизоном.
УФА В XVII - XVIII ВЕКАХ
На протяжении XVII и первых десятилетий XVIII века Уфа оставалась пограничной крепостью, выдвинутой далеко на юго-восток от общей линии укреплений России, и служила опорным пунктом в организации защиты государственных границ от набегов соседних кочевых народов.
XVII век
Постоянное население города в первой половине XVII века было небольшим. Некоторое представление о размерах города дает переписная книга Уфы 1647 года, в которой учтено всего 66 дворов. С учетом дворов стрелецкого отряда (около 100) общее количество дворов в городе вряд ли превышало 200. Основной состав населения был русский, но в числе первых уфимцев были и представители татар, башкир, мордвы и некоторое число иноземцев. Почти все они вскоре приняли христианскую веру ("новокрещеные").
Однако историю формирования г.Уфы невозможно представить без слобод, деревень и сел, появившихся на Уфимском полуострове и тесно связанных с городом. В самом начале XVII века в 18 км от города появляется небольшая деревня под названием Новая Слобода, которую основал Иван Кадомец (крещеный башкир). С 1613г. слободу стали называть Кадомцевой деревней. После постройки церкви в 1622 году деревня стала называться иначе - село Богородское. В дальнейшем Богородское стало весьма значительным селом, здесь находился волостной центр, была ежегодная ярмарка (ныне микрорайон ИНОРС).
С 1591-1592 годов в северной части современной Уфы в отводной книге упоминается "подгородная татарская слобода" на р.Урюзя. По имени основателя Шугур-Али Конкузова слободу начали называть Шугуровой деревней или просто Шугуровкой. Речку Урюзя тоже стали называть Шугуровкой (Шугуркой). Деревня ныне поглощена городом, а речка течет, хотя и обмелела.
В конце XVI или самом начале XVII века в числе служилых людей из Москвы приехал Иван Черников. Первый раз ему отвели земельную дачу в 1607 году. В 1615 году Черников подал царю челобитную с просьбой подтвердить ему старый отвод и заново оформить документально, записав в новую книгу. Пользуясь служебным положением (Черников служил дозорным, т.е. отводчиком и отмещиком земли), при новом оформлении он увеличил размеры владения. Деревне Черниковке суждено было в XX веке стать городом Черниковском, который впоследствии соединился с Уфой и образовал ее северную часть.
С ростом города старые кремлевские укрепления и примитивные оборонительные заграждения, возведенные вокруг слобод, стали недостаточными. К тому же дубовые укрепления кремля к середине XVII века обветшали и потеряли свою былую боеспособность. Решение о возведении новой оборонительной линии московское правительство приняло в 1664 году. Строительство новой крепости затянулось в связи с ее сравнительно большими размерами, так как стены должны должны были охватить все поселение, включая пригородные слободы. Новая крепость получила название "Нового" или "Большого" острога, кремль же стал называться "старым" или "верхним городом". Стены новой крепости были рублены из дуба и достигали высоты 2 сажен (более 4-х метров).
XVIII век
В начале XVIII века Уфа заняла видное место в сношениях России с казахскими жузами. В 1730 году хан Младшего жуза (с XVIв. группа западно-казахстанских племенных объединений) Абулхаир прислал в Уфу посольство с просьбой о принятии его в русское подданство. Переговоры завершились тем, что 10 октября 1731 года хан Абулхаир и старшины Младшего жуза принесли присягу русскому правительству.
В начале XVIII века город начинает расти в западном направлении - кварталы жилых жомов строятся за Ильинскими и Фроловскими воротами, плотно заселяется Шугуровская гора. Для связи ее с центром строится мост через Ногайский овраг, также получивший название Ногайского. К этому времени в Уфе насчитывалось уже свыше 650 дворов.
В 30-х годах XVIII века Уфа стала базой для строительства Оренбурга. В связи с организацией Оренбургского казачьего войска в новый город переводят 185 уфимских казаков. Создание Оренбургской линии крепостей привело к значительному отливу из Уфы и других групп служилого населения.
В связи с продвижением государственных границ далеко на юго-восток Уфа к середине XVIII века потеряла свое прежнее стратегическое значение, хотя и продолжала играть роль военного центра Башкирии. В 1736 году составляется новый план Уфимской крепости, по которому предполагалось вокруг города построить 12 земляных бастионов; овраги между горами планировалось перегородить двойной линией палисадов, в которых устроить створчатые ворота для спуска весенних вод. Но этот проект остался нереализованным, так же как и более ранний проект 1728 года, который предусматривал перенос укреплений на гору к западу от существующих. Были проведены только ремонтные работы и некотороя модернизация укреплений. Двойное кольцо оборонительных сооружений сохранялось вплоть до середины XVIII века.
Пожар 1759 года и его последствия
Губительным для кремля так же, как и для всего города, стал пожар 1759 года, сыгравший большую роль в изменении планировки Уфы. Пожар возник 23 мая от молнии, попавшей в Михайловскую башню кремля. с нее огонь перекинулся на другие тесно стоявшие деревянные постройки. Бедствие не ограничилось кремлем. Оно охватило ближайшие к нему улицы Малой Репной слободы и даже часть стен большого города. Всего сгорело 210 дворов.
В делопроизводстве Уфимской провинциальной канцелярии сохранилось подробное описание этого стихийного бедствия:
"... от которого (от пожара) состоявшая в кремле Михайловская башня, а от оной гоубтвахтная, караульная изба с сеньми и воеводский дом, так и канцелярия с некоторыми указами, протоколами, журналами и протчими делами и несколько гербовой и простой бумаги, да в соборной церкви несколько ж церковных украшений и на колокольне боевые часы, тюрьма с острогом, девичий монастырь з двумя церквами и протчее ... згорело".
После пожара кремлевские укрепления уже не восстанавливались, так как в них не было необходимости. Территория бывшего кремля превращается в административный центр города; между ним и жилыми кварталами оставляется свободная от застройки зона во избежание "опасных случаев".
Постепенно восстанавливаются поврежденные огнем укрепления большого города; они существуют вплоть до Крестьянской войны 1773-1775 годов. Возрождаются и жилые кварталы города. Окончательно оформляются его улицы и переулки. Именно в третьей четверти XVIII века они получают свои названия, хотя еще и неустойчивые. Некоторые улицы имеют двойные названия. Старые названия Репных улиц (по слободам) постепенно вытесняются употреблявшимися параллельно с ними названиями по дорогам: Малая Репная - Большой Казанской (ныне ул. Октябрьской революции), Большая Репная - Сибирской (ныне ул. Мингажева). Кроме них в 50-60-х годах существовали улицы: Ильинская (ул.Фрунзе), Фроловская (ул.Тукаева), Покровская (позднее Посадская) по правому берегу р.Сутолоки; на востоке за Сутолокой - Успенская (ул.Сочинская), Будановская (ул.Е.Сазонова), Кафтанова (возле р.Белой).