Герберштейн приехал в Москву через три недели после отъезда Загряжского в Ливонию, 18 апреля. Пятью месяцами раньше он вместе со своим племянником Иоганном фон Турн выехал из эльзасского города Гагенау для выполнения сложных и ответственных дипломатических поручений. Император поручил Герберштейну проводить к Сигизмунду свою внучку, миланскую принцессу Бону Сфорца, которая была обручена с польским королем. Далее он должен был сообщить королю о том, что император нашел способ уладить разногласия между Польшей и Тевтонским орденом и, наконец, в его задачу входило договориться с Сигизмундом об условиях, на которых мог состояться мир между Россией и Польшей.

Прежде чем попасть в Вильно, императорский посол заехал в Кенигсберг. Он встретился там с великим магистром Тевтонского ордена. Во время аудиенции Альбрехт попросил Герберштейна пере — дать королю Польши его личное послание. В этом послании Альбрехт вновь требовал у Сигизмунда возвращения Западной Пруссии. Он соглашался и на компенсацию: если король не захочет отдавать Западную Пруссию, он может вернуть Ордену Жемайтию. Несмотря на то, что просьба Альбрехта о передаче письма королю, по сути дела, превращала Герберштейна в посредника между Тевтонским орденом и Польшей и могла повредить успеху всей его миссии, императорский посол согласился исполнить это поручение. После этого Герберштейн и Бона поехали в Вильно.

Следует заметить, что когда возник вопрос о второй женитьбе короля Сигизмунда, среди польских прелатов и магнатов мнение по этому вопросу не были единым. Лаский настаивал на браке короля с мазовецкой княгиней Анной Пяст или ее дочерью. Одновременно, говорил Лаский, нужно выдать замуж за сыновей Анны Пяст дочерей короля Сигизмунда. Такая матримониальная комбинация обезопасила бы польский престол от посягательств со стороны Габсбургов. Однако Сигизмунд склонился на сторону Любранского и Шидловецкого, поддерживавших кандидатуру принцессы Боны. После этого Лаский выдвинул новый план. Он знал, что Бона Сфорца приносит с собой в виде приданного княжество Бари, расположенное в области Апулия, в самой крайней в юго-восточной Италии. А так как восточное побережье Италии, постоянно находилось под угрозой турецкого вторжения, он предложил перевести туда Тевтонский орден, обменяв Бари на Восточную Пруссию. Этот проект надлежало обсудить в Риме, ибо без ведома папы трудно было рассчитывать на его выполнение. Однако, папа не одобрил проект Лаского.

В первые дни по приезде в Вильно Герберштейну повезло: невеста пришлась по душе королю Сигизмунду. И, таким образом, наиболее деликатнее поручение императора было выполнено. Но другие поручения императорский посол выполнить не смог. Сигизмунд откровенно признался Герберштейну, что самым важным вопросом он считаем заключение мира с Россией. Он попросил императорского посла всячески содействовать заключению этого мира и передать Василию III, что поляки согласны вести переговоры или на русско-литовской границе, или в Риге, или во владениях датского короля. 14 марта императорский посол покинул Вильно, а 18 апреля въехал в Москву.

Уже через три дня, 21 апреля, Герберштейн был принят Василием III. Во время этой аудиенции императорский посол вначале, строго следуя полученной инструкции, заявил, что главной целью императора является объединение всех христианских государей для борьбы с турками. Теперь, сказал Герберштейн, Максимилиан достиг наивысшего могущества, ибо все государи Европы связаны с ним либо родством, либо узами дружбы. И только Сигизмунд и Василий враждуют между собой, ослабляя христиан и радуя язычников. После этого барон отошел от текста инструкции и прибавил от себя, что турецкий султан Селим Явуз разгромил войска египетского султана. Это добавление Герберштейн сделал, желая в глазах русских еще более усилить впечатление о размерах турецкой опасности. В заключение Герберштейн от имени императора предложил подписать с поляками вечный мир или же, на худой конец, хотя бы перемирие.