Воодушевленный успешным нападением на Очаков, Вишневецкий решил построить на одном из островов ниже днепровских порогов (Запорожье) казацкий форт. Такая цитадель была бы превосходной базой для действий против татар и турок. Вишневецкий выбрал для этого остров Хортицу, и там летом 1556 г. была выстроена казацкая крепость. Этим годом датируется первое известное упоминание о Запорожской Сечи (по-украински, Сичь) – так днепровские казаки называли свою крепость.437 После этого Вишневецкий попросил у Сигизмунда Августа денег и продовольствия, чтобы обеспечить защиту Хортицы от татар, но, не получив помощи, покинул остров и возвратился в Черкассы. Вскоре после этого (в сентябре 1557 г.) он направился в Москву и предложил свои услуги царю. За поддержку Иван IV даровал Вишневецкому город Белев на Верхней Оке. Стратегическое расположение Белева являлось удобной базой для ведения степной кампании в правлении как днепровских, так и донских земель. В январе 1558 г. Вишневецкий с отрядом русских казаков и московских стрельцов был послан к Перекопскому перешейку. Экспедиция ни к чему не привела, и Вишневецкий отправился на Хортицу, где к нему присоединились войска под предводительством дьяка Ржевского. Вдвоем они совершили еще один поход на Перекоп, но их сил для штурма оказалось недостаточно, и они возвратились в район Среднего Днепра. Царь приказал Вишневецкому прибыть в Москву, оставив Ржевского в районе Днепра. По-видимому, лагерь Ржевского находился на Монастырском острове выше порогов.438
Должно быть, к этому времени царю стало ясно, что любое нападение на Крым по Днепру требует более тщательной подготовки и хорошо организованной базы в Запорожье. Чтобы избежать каких-либо разногласий с Литвой, ему, прежде чем предпринимать какие-либо действия в днепровских землях, нужно было с ней договориться.
В феврале 1558 г. царь Иван IV послал в Вильно к Сигизмунду Августу «сына боярского» Романа Олферьева с предложением объединиться против крымских татар.439 Олферьев прибыл в Вильно в мае и был хорошо принят. Однако крупные литовские собственники, несомненно с подозрением относившиеся к связи царя с Вишневецким и к вмешательству Москвы в ливонские дела, не дали никакого определенного ответа. Олферьеву сказали, что вопрос о союзе не может быть сейчас решен, и что король (и великий князь) хотел бы направить своего посланника к царю для дальнейших переговоров.
Литовцы особенно были озабочены ливонской ситуацией, поскольку сами были в нее вовлечены. В 1557 г. Сигизмунд Август вмешался в столкновение между магистром ливонских рыцарей, престарелым Вильгельмом Фюрстенбергом, и архиепископом Риги Вильгельмом. Брат последнего, Альбрехт, герцог Пруссии, был вассалом Польши. И архиепископ и Альбрехт состояли в родстве с Сигизмундом Августом по линии их матери, сестры короля. Сигизмунд повел объединенную польско-литовскую армию в Ливонию. Фюрстенберг запросил мира и согласился заключить военный союз с Польшей и Литвой.