В середине XVI века состоялось вхождение Башкирии в состав многонационального Русского государства. Управление Башкирией (Уфимским уездом) осуществлялось в ту пору Приказом Казанского дворца, созданного после присоединения Казанского ханства к Русскому государству.
    Однако отдаленность уезда от Казани затрудняла управление обширным краем и его защиту от набегов соседних враждебных кочевников.
    Вот почему башкиры в 1573 году обратились к царю Ивану Грозному с просьбой о строительстве на их земле города. Гарнизон города-крепости мог бы защитить башкир от набегов степняков, а сам город стал бы местом уплаты ясака, который раньше возили в далекую Казань.
    Первый историк башкирского края П. И. Рынков так писал об этом: "По достоверным выправкам нашлось, что башкирцы о построении сего города челобитье свое имели в 7081 году (то есть от Рождества Христова 1573) не только для того одного, чтобы им положенный на них ясак тут, как внутри их жилищ, платить было льготнее, но и от неприятелей бы иметь им здесь убежище и защиту".
    Различные источники, в частности башкирские шежере, не только подтверждают это, но и свидетельствуют о том, что башкиры с подобными просьбами обращались и ранее. Так, после 1569 года из Казани был послан Иваном Грозным в Уфимский уезд Иван Васильевич Артемьев "по просьбе башкирцев для очерчивания и построения города Уфы". Почему же после присоединения Башкирии к Русскому государству на ее территории так долго не строились крепости и города?
    "Добровольный характер присоединения Башкирии к России не вызывал надобности немедленной постройки крепостей и городов с размещением в них военных гарнизонов, - пишет историк А. Н. Усманов. - Однако со временем возникла настоятельная необходимость в постройке города на земле башкир. В этом были заинтересованы как сами башкиры, так и русское правительство". Заинтересованность башкир в постройке города понятна: это связано с уплатой ясака и защитой их от набегов.     Какие же цели преследовало московское правительство, приняв решение о строительстве Уфы?
    Историк Р. Г. Буканова считает, что такими целями для Москвы были: усиление своего влияния в Башкирии и прекращение притязаний сибирских и ногайских феодалов на башкирские земли; предотвращение выступлений недовольных зависимостью от России части башкирских феодалов.
    Основная же цель определялась задачами, стоящими перед государством на Востоке в XVI - XVIII веках. Нужно было продвигаться в Сибирь, а затем в Казахстан и Среднюю Азию. А Башкирия занимала значительную часть юго-восточных рубежей страны. Чтобы двигаться на Восток, нужно было сначала закрепиться в Башкирии, сделать ее опорным пунктом и удобным стратегическим плацдармом. Вот почему и возникла необходимость в постройке города в Башкирии, административного центра большого края.
    По просьбам башкир царь Иван Грозный направил в 1574 году в Башкирию отряд русских стрельцов под руководством выборного дворянина, городового воеводы, позднее воеводы в Сибири Ивана Григорьевича Нагого и его сопровождающего боярского сына Константина Голубцова. В православный праздник Пресвятой Троицы (6 июня по старому стилю), высадившись со стругов, московские стрельни на берегу Белой Воложки при впадении в нее реки Сутолоки основали новую русскую крепость - кремль-детинец "для защиты башкир от нападения и вторжения сибирских народов, ногаев и киргиз-кайсаков". Уже в 1575 году стрельцы отбили набег сибирских царевичей Аблая и Тевкеля, стремившихся помешать строительству Уфимской крепости.
    Первая попытка утверждения над ногайскими башкирами московского господства, свидетельствует историк М. К. Любавский, была сделана в 1574 году, когда московский воевода Иван Нагой, посланный на реку Уфу, заложил при впадении Уфы в Белую город Уфу.