Несмотря на этот успех, положение Подковы все более ухудшалось. В Валахии сосредоточивались турецкие войска и дружины отступивших туда верных Петру Хромому бояр. На помощь Петру Хромому двигалось войско семиградского воеводы — племянника польского короля Стефана Батория. Подкова, располагая значительно меньшими по сравнению с противниками силами, вынужден был покинуть Молдавию. 31 декабря 1577 г., оставив Яссы, Подкова двинулся на Сороки, а затем вернулся в Немиров. Он не переставал надеяться на возможность договориться со Стефаном Баторием о совместном выступлении против Турции.
Из Немирова Иван Подкова по совету брацлавского старосты отправился в Варшаву, но по дороге был арестован. Стефан Баторий, занятый в это время приготовлением к сейму, где должны были обсуждаться вопросы, связанные с продолжением войны против России, приказал бросить Подкову в тюрьму. Король не сразу решился покончить с Подковой ввиду крайнего возбуждения, царившего среди народа, который сочувствовал антитурецкой позиции Подковы. Однако Стефан Баторий вынужден был выполнить волю султана, приславшего чауша (дипломатического агента) с требованием выдать Подкову Турции или казнить его. Такая позиция османских политиков вызвала возмущение даже у шляхты, которая, по словам Иоахима Бельского, «очень жалела этого Подкову, ибо был он муж добрый». Кроме того, высокомерное требование султана задевало политический престиж Польши как суверенного государства. Тем не менее король, обвиняемый султаном в потворстве Подкове и казакам в походе на Молдавию, не решился отклонить требование падишаха в ответственное для Польши время подготовки нового выступления против России.
Свидетель переговоров польского правительства с турецким посланцем ксендз Ян Пиотровский сообщал: «На днях приехал турецкий чауш и на завтра же имел аудиенцию, бранится, грозит; падишах пишет, чтобы мы прислали в Константинополь или Подкову с Константином (молдавский сподвижник Подковы. — Ред.) живьем, или их головы; поэтому тут Подкове уже конец». В другом письме Ян Пиотровский, выражавший, видимо, настроение шляхетства, писал: «Бедняга Подкова должен быть казнен и, наверное, или еще в бытность чауша, или тотчас после отъезда будет ему отрублена голова». Казнь Подковы произошла во Львове на Рыночной площади 18 июня 1578 г. — через пять месяцев после заточения его в тюрьму.
Польское правительство, опасаясь возможных попыток со стороны шляхты и простого народа освободить Подкову, предприняло соответствующие предупредительные меры, однако на Рыночной площади во Львове собралась огромная толпа. Обратившись к ней, Подкова сказал, что он всю свою жизнь боролся против турок и действовал всегда на благо страны, а казнят его потому, что «турок… так приказал Вашему королю, как своему подданному». «Польша, — продолжал он, — еще испытает много несчастий от такой услуги султану». Многие в толпе плакали, особенно «воины, которые прибыли сюда ради него, но не могли ему помочь из-за больших приготовлений, проведенных правительством».
Казнь Подковы произвела сильное впечатление на народ. По этому поводу Ян Пиотровский писал: «Удивительное дело, как вся здешняя чернь сожалеет о нем: печатают о нем книги, песни. Живописцы нарисовали его обезглавленное тело».
Еще в то время, когда Подкова находился в заключении, в Молдавии произошли важные события, известия о которых находим в письме султана польскому королю от марта 1578 г. В нем говорится, что некий человек (как потом стало известно, Александр, выдававший себя за брата Ивони Лютого и Подковы. — Ред.) во главе более 2 тыс. пеших и конных казаков из-под Киева, Канева, Черкасс и Брацлава, вооруженных огнестрельным оружием, ворвался в Молдавию, наполнил край пожаром и войной и, наконец, расположившись в прилегающей к Яссам местности, опоясал город цепью отрядов и подверг его тесной блокаде. Петру Хромому, вновь занявшему молдавский трон, удалось бежать из Ясс. Александр вступил в столицу Молдавии. Через месяц, однако, войско Александра потерпело поражение, а сам он попал в плен. Турки посадили его на кол, а захваченных казаков отправили в Константинополь.
Деятельность Подковы сохранилась в памяти украинского народа. В сознании последующих поколений он выступает как мужественный предводитель украинского казачества в борьбе против турецкой агрессии. Н. В. Гоголь писал, что память «про молодецкие дела Подковы» жива в народе. Т. Г. Шевченко одно из лучших своих произведений, посвященных борьбе украинских казаков против турок, назвал «Иван Подкова», а И. Франко видел в совместной борьбе казаков и молдаван «свидетельство прошлого братства по оружию».