По отъезде Генриха в Польше не знали, что делать: объявлять ли бескоролевье или нет? Решили бескоролевья не объявлять, но дать знать Генриху, что если через девять месяцев он не возвратится в Польшу, то сейм приступит к избранию нового короля. В Москву поспешили отправить от имени Генриха послов с известием о восшествии его на престол и вместе с известием об отъезде во Францию, причем будто бы он поручил панам радным сноситься с иностранными государями. Иоанн отвечал, что уже отправил в Польшу гонца своего Ельчанинова с требованием опасной грамоты для послов, которые должны ехать к Генриху поздравлять его с восшествием на престол; что Ельчанинов будет дожидаться возвращения короля, а у панов радных не будет: государь ссылается только с государем, а паны - с боярами; если же прежде была ссылка между ним, Иоанном, и панами, то потому, что у них не было короля и они присылали бить челом, прося его или сына его на господарство, но теперь есть у них король, мимо которого с панами ссылаться непригоже. Ельчанинову долго было дожидаться Генриха; он дождался сейма, во время которого пришел к нему тайно ночью литовский пан, староста жмудский, и говорил: "Чтобы государь прислал к нам в Литву посланника своего доброго, а писал бы к нам грамоты порознь с жаловальным словом: к воеводе виленскому грамоту, другую - ко мне, третью - к пану Троцкому, четвертую - к маршалку Сиротке Радзивиллову, пятую - ко всему рыцарству, прислал бы посланника тотчас, не мешкая; а королю Генриху у нас не бывать. Я своей вины пред государем не ведаю ни в чем, а государь ко мне не отпишет ни о каких делах и себе служить не велит; нам безмерно досадно, что мимо нас хотят поляки государя на государство просить, а наша вера лучше с московскою сошлась, и мы все, литва, государя желаем к себе на государство. Если мы умолим бога, а государя упросим, что будет у нас в Литве на государстве, то поляки все придут к государю головами своими бить челом; а государю известно, что когда у нас прежде был король Витовт, то он всегда жил в Вильне; и теперь нам хочется того же, чтоб у нас король был в Вильне, а в Краков бы ездил на время; но государь как будто через пень колоду валит". Далее староста говорил, что Литва, согласно царскому желанию, хочет избрать императорского сына, но поляки хотят выбрать приятеля султанова; говорил, что им трудно принять условие относительно наследственности короны в потомстве царя; но если они милость и ласку государскую познают, то от потомства его никогда не отступят, хотя бы и другой народ не согласился; потом еще жестоко людям кажется то, что государь говорит о Киеве и Волынской земле и что венчать его на царство будет митрополит московский. Из поляков Яков Уханский, епископ гнезненский, прислал Ельчанинову образцы грамот, какие царь должен прислать к духовенству, панам, ко всему рыцарству и к каждому пану в особенности; в общих грамотах Иоанн должен был просить об избрании, обозначить в грамоте, что он не еретик, а христианин, крещен во имя св. троицы, что поляки и русские, будучи одного племени, славянского или сарматского, должны, как братья, иметь одного государя. Замечательны образцы грамот к некоторым вельможам; например, к одному царь должен был написать: "Ты меня знаешь, и я тебя знаю, что у тебя большая сума (калита); я не калиты твоей хочу, хочу тебя иметь своим приятелем, потому что ты умный человек на всякие дела, умеешь советовать так, что не только калита, но и сундуки будут".
Иоанн находился в затруднительном положении: с одной стороны, тяжело ему было унизиться до искательства, неверен был успех и затруднительно положение в случае успеха; с другой - неприятно было и видеть себя обойденным, особенно когда выбор падет на человека нежеланного, с которым надобно будет опять начинать войну за Ливонию. Выслушавши донесение Ельчанинова, царь приговорил послать гонца Бастанова к панам с требованием опасной грамоты для больших послов. Бастанов доносил, что, по всем слухам, литовская Рада хочет выбирать московского государя; папский нунций доносил в Рим, что вельможи ни под каким видом не хотят московского царя, но народ показывает к нему расположение; в другом письме доносил, что московского государя желает все мелкое дворянство, как польское, так и литовское, в надежде чрез его избрание высвободиться из-под власти вельмож. Узнавши от Бастанова о возможности успеха, Иоанн велел немедленно отпустить в Польшу посланника Новосильцева с грамотами к Уханскому, к краковскому архиепископу и светским панам; в грамоте к Уханскому царь уверял, что веры и почестей духовенства не порушит, самому Уханскому обещал большие награды, если его старанием будет избран в короли: "Мы тебя за твою службу почестями и казною наградим; дай нам знать, какого от нас жалованья хочешь, и мы станем к тебе свое великое жалованье держать". Но одних обещаний частным лицам было мало; Иоанн ни слова не говорил, отказывается ли он от прежних своих условий, а на сейме не хотели слышать ни о каких других условиях, кроме тех, на которых был избран прежде Генрих; кроме того, Новосильцев был посланником легким и потому не мог так действовать, как действовали уполномоченные других соискателей. Эти обстоятельства опять произвели то, что сторона московская, особенно между поляками, упала и выдвинулись вперед две стороны: сторона вельмож, которые хотели избрать императора Максимилиана, и сторона шляхты, хотевшей избрать Пяста, т. е. кого-нибудь из природных поляков или по крайней мере не австрийца, не кандидата стороны вельможеской.