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