Запорожці радо вітали заміри Вишневецького, прибули до нього на Хортицю, обрали його своїм гетьманом та обіцяли міцно стояти разом із ним у боротьбі з бусурманами.
Острів Хортиця чималий: він тягнеться на десять верст уздовж і шириться на три версти впоперек. Його голова (горішній кінець) дуже висока й виходить із води сторчовими скелями, неприступними для ворогів. Саме тут Вишневецький і почав споруджувати містечко, обкопуючи його рівчаками та обсипаючи валами; коли ж містечко було закінчене, козаки поробили з дубових кряжів ще поверх валів стіни та башти. Те містечко простягалося від голови острова до Вошивої скелі на східній протоці Дніпра та до острова Мала Хортиця на заході, який зветься у наші часи Старим Дніпром, і поділявся такими ж окопами та стінами упродовж острова на дві частини з тим, щоб коли вороги здеруться на острів з одного боку, то на іншій половині можна було б оборонятися.
Закінчивши ту велику й міцну будову, Вишневецький звернувся з листами до польського короля Жигмонта й до московського царя Івана Грозного, щоб вони надали йому підмогу для великого походу в Крим.
Надії Вишневецького на допомогу не здійснилися. Король не тільки не допоміг, а ще й розгнівався за те, що гетьман зачіпає татар; цар же хоча й прислав запорожцям на потугу путивльських козаків, але та поміч була дуже незначна.
Проте року 1556-го Байда вирушив-таки походом на Очаків і, зруйнувавши його околиці, визволив чимало невольників. Тільки через брак гармат йому не вдалося добути Очаківський замок. Повернувшись із походу, Вишневецький негайно ж напав на Аслам-город та тільки й цього міста не взяв, а, обминувши його, обійшов із козаками всі татарські степи й попалив улуси до самісінького Перекопу.
Відплачуючи за ті козацькі напади, хан кримський наприкінці того ж року, діждавшись, доки Дніпро замерзне навколо Хортиці, атакував із великою ордою містечка Вишневецького, але захопити їх не зміг. Козаки цілий місяць давали татарам відсіч і, добре погромивши ворога, врешті-таки відігнали геть.
По весні, радіючи своїй перемозі, запорожці посідали в човни, несподівано підпливли до Аслам-городу, взяли його штурмом і, повигинавши всіх бусурманів та визволивши чимало невольників, повернулися на Хортицю з великою здобиччю.
Та недовго запорожці святкували перемогу. Через півроку Хортицю оточили вороги; зі сходу підступив хан з ордою, з півдня на сандалах і галерах прибули турецькі яничари, а із заходу підсунулося волоське військо, підвладне султанові.
Тяжко довелося козакам одбиватися від ворогів, бо тих було вдесятеро більше, допомога ж ні від короля, ні від царя не прийшла, проте запорожці міцно стояли й одбивалися, не шкодуючи свого життя, і лише через чотири місяці, коли на Хортиці не вистачило припасів, Вишневецький потай покинув острів і подався з городовими козаками до Черкас, а запорожці попливли у Великий Луг до своєї добре прихованої й не відомої ні татарам, ні туркам Січі.
Перебувши ці пригоди, Вишневецький зрозумів, що для боротьби з бусурманами козацької сили замало. Проте він не заспокоївся на тому, а, впевнившись, що московський цар прихильніше ставиться до його боротьби, ніж польський король, поїхав у Москву, записався в царя на службу й, діставши від нього клейноди Війську Запорозькому та невеличку допомогу військом, року 1558-го знову повернувся на Хортицю та, згуртувавши біля себе городових і запорозьких козаків, вирушив на татар степами й Дніпром. Наляканий бойовим хистом та завзяттям Вишневецького, кримський хан залишив цього разу козакам усі дніпровські міста й степові улуси й, зібравши свої орди, заховався з ними в Криму.
Козаки з Вишневецьким опанували всіма степами, починаючи від Бугу й до самісінького Дону, і звідтоді стали мати їх за свою власність. Проте таке становище тривало недовго, бо московський цар викликав свого підданця Вишневецького до Москви й послав його з російським військом воювати на Кавказ, а татари ж тим часом знову вийшли з Криму й захопили свої кочовища.
Через рік Іван Грозний хотів послати Вишневецького зі своїм військом проти Польщі, та тільки гетьман на те не згодився, а, зачувши, що на Україну з Буджака наскочила татарська орда, знову прибув на Запорожжя й року 1561-го листом із Січі Запорозької просив короля Жигмонта повернути його в своє підданство. Король охоче виконав те бажання, покликав Вишневецького до себе у Краків і там з великою пошаною привітав його, разом із найвищою польською шляхтою, як відважного войовника-лицаря.
Після того Байді було повернуто всі його маєтки, але все-таки пильно завважено не водити більше козаків на татар і турків, щоб не піднімати їх на помсту. Вишневецький скорився волі короля, але ненадовго. Життя в розкошах та багатстві не задовольняло завзятого козацького ватажка, і за першої ж нагоди, незважаючи на свої не молоді вже роки та недуги, він знову взявся за шаблю.
Сусідня з Україною земля — Молдова, що тоді була в залежності від турецького султана, хотіла, проти волі свого господаря, себто князя, скинути турецьке ярмо — і от молдавські бояри, шукаючи собі підмоги, прислали до Вишневецького посланців просити, щоб він, набравши військо, став господарем Молдови й уладнав її спілку з Польщею.
Вишневецький охоче на те відгукнувся й удався за згодою до Війська Запорозького. Поклик улюбленого гетьмана, що не раз водив козаків до слави, відразу підняв на ноги запорожців, і навколо Вишневецького зібралося біля 4000 душ. З тим військом року 1564-го він і вирушив на Молдову, та тільки там на нього чекала зрада. Другий претендент на Молдавське господарство, боярин Томжа, сподіваючись собі ласки від турецького султана, вдав із себе спільника Вишневецького, а коли той із невеликою купкою запорозької старшини та польської шляхти відступив від свого війська й наблизився до Томжі, він захопив Байду з усією старшиною в бранці й мерщій надіслав у дарунок турецькому султанові.
Довідавшись про зраду, запорожці кинулися на військо Томжі, але, побачивши, що наздогнати й визволити з неволі славного товариша було вже неможливо, мусили із сумом повернутися на Україну.