К строительству Самарской крепости готовились полтора-два года. В конце апреля – начале мая 1586 года караван судов, из-под Свияжска, отправился в путь. Главным помощником Засекина в том походе был стрелецкий голова Фёдор Ельчанинов, с которым они участвовали в подавлении черемисского восстания.

Поперву хотели строить крепость в Самарском урочище, где река Самара впадала в Волгу. В этом случае крепость была защищена от внезапного нападения кочевников протоками и озёрами. Но, осмотрев всё более внимательно, князь Засекин начал строить крепость вдалеке от Волги на возвышенности, которую все называли «горой».

Датой основания нового города считается праздник Троицы, который в 1586 году пришёлся на 22 мая (1 июня по новому стилю). Потому как, именно в этот день началось строительство, как крепости, так и первого самарского храма – Пресвятой и Живоначальной Троицы. Появление крепости на Волге (в том же году на реке Белой была построена Уфа) не на шутку огорчило ногайского бия Уруса. Новый ногайский бий – Урус в 1585 году предлагал даже Крымскому хану заключить союз и пойти в поход на Астрахань, чтобы при поддержке турецкого султана лишить Россию Нижней и Средней Волги. Посланники из Москвы, да и сам Григорий Засекин всячески убеждали его послов в том, что она построена только для борьбы с казачьей вольницей. Бий не верил.

Дело шло к большой войне, и Москва решила использовать в качестве «вестников мира» казаков. Летом 1586 года волжско-яицкие казаки во главе с Матюшей Мещеряком совершили ряд набегов на ногайские станы. А потом и вовсе замыслили неслыханное: построить город на Кош-Яицком острове на реке Илек (Урал). Бию Урусу стало не до Самары. Он пошёл на штурм нового казачьего городка, но потерпел сокрушительное поражение.

Уже после победы казачьего войска над Урусом, к его атаманам доставили царскую грамоту, которая призывала их поступить на государеву службу. Мнение разделились. Часть казаков во главе с атаманом Матвеем Мещеряком приняла предложение и прибыла в Самару. Но большинство во главе с Богданом Барбошей осталось на Яике.

Прибывших в Самару казаков хотели отправить в Астрахань, но вмешался случай. От Мещеряка потребовали, чтобы ногайцам вернули пленных и награбленное за год имущество. По стечению обстоятельств, в то же время из Москвы через Самару возвращалось ногайское посольство. Степнякам было бы приятно вернуть себе все отнятое казаками, а царь и Боярская Дума получали прекрасный повод, показать себя друзьями бия Уруса. Но атаман Матвей Мещеряк и его товарищ Тихон Пиздёша не подчинились, объясняя, что все награбленное досталось им в честном бою, и что, казаков на ногайцев «натравила» сама Москва.

Совсем обезумев, казаки и вовсе стали издеваться над прибывшими в Самару ногайскими послами: «всякие непригожие дела говорить… как жён их соромотили», за пленников потребовали огромный выкуп, а, в конце концов, попытались их ещё и ограбить.

Григорий Засекин был вынужден бросить пятерых самых буйных казаков в тюрьму, а остальных отправить в Астрахань. Держать видных атаманов в узилище было опасно. В любой момент им на выручку могли прийти казаки с Яика. Что-то предпринимать без царской грамоты Засекин также не мог. Пленённые же казаки не сидели, сложа руки. Они вступили в сговор с частью гарнизона Самарской крепости. План был прост: «послать» весть всем вольным казакам Волги и Яика, чтобы те подошли к Самаре и взяли крепость штурмом.

Однако среди заговорщиков нашёлся предатель, который сообщил князю Засекину о готовящемся заговоре. Григорий Осифович немедленно сообщил об этом в столицу. Рассмотрение дела заняло немного времени, и в марте 1587 года в Самару прибыл сын боярский Постник Косяговский с царским вердиктом: «Матюша Мещеряка да Тимоху Пиздяшу, да иных их товарищей пущих (государь) велел казнити перед ними послы смертною казнию». Приговор привели в исполнение весной 1587 года. Ногайские послы вернули себе все отнятое казаками и убедились в лояльности русской администрации. Был, достигнут и столь долгожданный для Москвы мир. Многие ногайские мурзы оставили мысли о самостийности и начали посылать свои отряды на службу в русскую армию.