В это время уже существовали другие ближайшие города - Мценск, Пронск (ныне село Рязанской области), Дедославль (ныне село Дедилово, Тульской области), Белев и некоторые другие. Тула - ровесница Москвы, и ее исторические судьбы тесно связаны с процессом объединения русских земель вокруг Москвы и развитием централизованного Русского государства.
По некоторым данным город Тула был основан первоначально 16 километрами севернее его современного местоположения, на р. Тулице, от которой он мог получить свое наименование. Название речки Тулицы примечательно. Она действительно как бы пряталась (тулилась, скрывалась) в тогдашних непроходимых лесах в болотистой, поросшей осокой, пойме, временами появляясь и затем опять исчезая.
В последующем городская селитьба переместилась к югу, к месту впадения Тулицы в Упу и на левобережье последней. Здесь, на острове, образованном двумя рукавами реки Упы, черниговские князья заложили дубовую крепость (городище, острог).
Позже, в XIII веке, Тула вместе с восточной частью Тульского края была захвачена рязанскими князьями.
Положение Тулы на южной окраине формирующегося Русского государства всегда было тревожным, беспокойным. Город переходил из одних рук в другие. Он страдал при нашествии Батыя (1237 г.), Тохтамыша (1382 г.), на него совершали опустошительные набеги крымские и ногайские татары. Тульскую землю топтали и литовские завоеватели. В середине XIV века в течение 20 лет Тула числилась во владениях Тайдулы, жены татарского хана Чанибека. После Куликовской битвы (1380 г.) город перешел к Москве, но позже опять был захвачен рязанскими князьями. Лишь в 1503 году по завещанию рязанского князя Федора Васильевича Тула отошла к Московскому княжеству.
С вхождением в состав Московских владений Тула оказалась в стратегическом центре борьбы русского народа с кочевниками. Через Тулу проходил так называемый «Муравский шлях» (шлях - дорога, путь) - опасная дорога, по которой крымские татары совершали свои набеги на Москву. Это вынудило московских князей обратить самое серьезное внимание на укрепление Тулы. Старое городище в западной части острова на Упе не могло надежно служить делу защиты южных рубежей Москвы. К тому же, к концу XV века Тула переросла свою границу в рамках острова на Упе и все более перемещалась на левобережную (южную) часть реки.
В 1509 г. великий князь Московский Василий III приказал поставить на левом берегу Упы «город на Туле деревян». Город тогда представлял собою дубовую крепость («острог»), охватывавшую почти все поселение (без городища на острове). Ее замкнутый периметр тянулся на протяжении около двух километров по нынешней Советской улице, от ее начала около реки, примерно до проспекта Ленина и следовал далее, примыкая с внутренней стороны к земляному валу до Николо-Завальской церкви (т. е. церкви за валом), откуда поворачивал к реке, следовал вдоль берега на запад и соединялся с началом крепости.
Крепость была вооружена пищалями, пушками и картечницами, установленными на 16 башнях и бойницах. 7 проезжих ворот из острога вели на старинные торговые дороги в Дедилов, Крапивну и Павшино. По этим оживленным путям передвигались вооруженные отряды московских войск, постоянно занятых охраной подходов к Туле от татарских набегов; по ним тянулись к городу крестьянские возы, направляясь к городскому рынку. Проезжие ворота и «пролазы» (для пешеходов) в стене соединяли дубовую крепость с прилегающим к ней посадом, население которого состояло из ремесленников и торговых людей.
Для усиления охраны Тулы «на пятое лето» (после сооружения крепости), т. е. в 1514 г., тот же Василий III, по словам Воскресенской летописи, «поставиша град камеи» (кремль) внутри дубовой крепости в качестве ее цитадели. В 1520 г. строительство кремля заканчивается; «того же лета свершиша град на Туле камеи».