Вместе с Герберштейном великий князь отправил к императору посла своего, дьяка Племянникова, который привез с собою новых послов Максимилиановых – Франциска да Колло и Антония де Конти. И Франциск да Колло, подобно Герберштейну, витиеватою речью старался склонить великого князя к миру, преимущественно выставляя ему на вид опасность со стороны турок для всей Европы, и особенно для России по соседству ее с татарами, имеющими одинакую веру и одинакие обычаи с турками. Но когда приступили к делу, то встретили те же самые затруднения: опять императорский посол настаивал на том, чтоб великий князь уступил королю Смоленск, опять бояре объявили, что Василий никогда этого не сделает. Не успевши относительно вечного мира, послы объявили, что так как император со всеми королями и князьями установили между собою перемирие на пять лет для общего дела, против христианского врага – турок, то не угодно ли будет и великому князю заключить с польским королем перемирие на пять лет. Великий князь соглашался на это перемирие, с тем чтоб каждый остался при том, чем владел до сих пор, и чтоб пленным была свобода на обе стороны; но король никак не согласился на последнее условие, имея в руках своих много знатных пленных, взятых на Оршинском бою. Таким образом, и вторые императорские послы уехали из Москвы, ничего не сделав; великий князь отправил к Максимилиану посла, дьяка Борисова, с предложением прекратить военные действия от Рождества Христова 1518 до Рождества 1519 года, чтоб тем временем продолжать переговоры; но смерть Максимилиана прервала сношения. И при Василии союзный договор с австрийским домом остался так же бесполезен, как и при Иоанне III; Максимилиан не только не исполнил главного условия договора – действовать против Сигизмунда заодно с Василием, но даже, принявши на себя роль посредника, явно держал сторону Сигизмунда. Причину такого поведения он высказал в письме своем к великому магистру Альбрехту: «Не хорошо, если король будет низложен, а царь русский усилится».

Долго сдерживаемый императором, который и его манил все надеждою мирного решения распри, Альбрехт решился наконец приняться за оружие, послал сказать Максимилиану, что не может терпеть дальнейшей отсрочки, а в Москву отправил вторично Шонберга с просьбою о безотлагательной высылке денег, необходимых для начатия войны. Великий князь приговорил с братьями и боярами, что нужно помочь магистру казною, и послал во Псков деньги на 1000 человек пехоты, распорядившись, однако, так, что деньги эти тогда только могли быть отправлены к магистру, когда последний действительно начнет войну с Польшею. Магистр просил также, чтоб великий князь известил короля французского о союзе своем с Пруссией; Василий согласился, и написана была такая грамота, первая из Москвы во Францию: «Наияснейшему и светлейшему великому королю галлийскому. Присылал к нам Альбрехт, маркграф бранденбургский, высокий магистр, князь прусский, бил челом о том, чтоб мы изъявили тебе, как мы его жалуем. И мы даем тебе знать об этом нашею грамотою, что мы магистра жалуем, за него и за его землю стоим и вперед его жаловать хотим, за него и за его землю хотим стоять и оборонять его от своего недруга, Сигизмунда, короля польского; а которые прусские земли, города наш недруг, Сигизмунд-король, держит за собой неправдою, мы хотим, чтоб, дал бог, нашим жалованьем и нашею помощию те города были за прусским магистром по старине. Объявил нам также высокий магистр прусский, что предки твои тот чин (орден) великим жалованьем жаловали: и ты б теперь, вспомнив своих предков жалованье, магистра жаловал, за него и за его землю против нашего недруга, Сигизмунда-короля, стоял и оборонял с нами заодно». Эти переговоры шли весною 1518 года. С известием о решении великого князя помочь Ордену при самом начале войны поехал в Кенигсберг московский посол Елизар Сергеев, которого Альбрехт просил поклониться великому князю до земли, не головою только, но и всем телом. Однако этот Елизар, возвращаясь из Пруссии, дал знать во Пскове, чтоб денег магистру не отправляли, потому что он войны еще не начинал. И действительно, в ноябре 1518 года магистр прислал великому князю грамоту с уведомлением, что у государей христианских идут переговоры о мире, об общем союзе против неверных, но что он не приступит ни к каким соглашениям без воли государя московского; а в марте 1519 года приехал в Москву в третий раз Дидрих Шонберг с объявлением, что явился новый посредник, папа, которого легат Николай Шонберг старается склонить всех государей христианских к союзу против турок, что Альбрехту папа предлагает предводительство над союзным христианским войском, которое должно действовать против неверных в Венгрии, и что поэтому ему было бы очень выгодно заключить мир с Польшею, но что он полагается во всем на волю великого князя и в ожидании ответа из Москвы не отмолвил папе и не объявил своего согласия, но отвечал, что отправит в Рим своих послов. Альбрехт предлагал великому князю заключить с королем перемирие на пять лет; впрочем, если великий князь предпочтет продолжать войну, то он, магистр, останется его верным союзником и начнет с своей стороны войну с Польшею, но в таком случае Шонберг должен взять у великого князя обещанные деньги и уговориться, каким образом вести войну. Шонберг выпросил новую грамоту к французскому королю в более учтивых выражениях и дал образец, как написать ее; выпросил также грамоту к курфюрстам и князьям Империи с изъявлением желания, чтоб новый император, которого изберут они на место Максимилиана, соблюдал договор предшественника своего с московским государем и покровительствовал ордену Тевтонскому, учрежденному для защиты германского народа; наконец, выпросил позволение послать одного из подданных магистра в Новгород или Псков, чтоб у кого-нибудь из тамошних священников выучиться русскому языку и грамоте.

С ответом на третье Шонбергово посольство отправился к магистру московский посол Замыцкий. Великий князь велел сказать Альбрехту, что он готов заключить перемирие на приличных условиях, но чтоб магистр во всяком случае не забывал своей клятвы. Замыцкий так описывал своей прием: «Магистр принял меня с великою честию, сам ко мне пришел и речей слушал, сам меня к себе к столу провожал и шел от меня по левую сторону, за столом посадил на своем месте». Альбрехт дал знать великому князю, что общее вооружение против турок не состоялось, следовательно, незачем заключать перемирие с Сигизмундом; что он, магистр, в июле или августе непременно начнет войну и пойдет на Данциг, для чего просил о немедленной высылке денег. После неоднократного повторения этой просьбы великий князь велел отправить деньги в сентябре 1519 года. Когда великий магистр дал знать магистру ливонскому, чтоб он велел проводить московского посла с деньгами, то Плеттенберг отвечал: «Я к московскому государю живу поближе прусского магистра и русский обычай знаю: на словах сулят, а на деле не исполняют». Когда же ему сказали, что московский посол действительно приехал в Ригу с деньгами, то Плеттенберг встал с места и, подняв руки к святым, сказал: «Слава тебе, господи, что великий государь царь всея Руси такое жалованье великому магистру оказал: надобно нам за его жалованье головами своими служить!»

Альбрехт начал войну с Польшею; узнавши об этом, великий князь послал ему денег еще для найма 1000 человек пехоты; но с одною этою помощию ослабевший Орден не мог противиться Сигизмунду. Стесненный последним, Альбрехт должен был войти с ним в мирные соглашения, вследствие которых получил орденские земли в наследственное владение, но с вассальными обязанностями к Польше. Так рушился окончательно знаменитый Тевтонский орден, имевший по отношениям своим к Литве такое важное значение в нашей истории.

Союз с Альбрехтом был по крайней мере полезен тем для Московского государства, что развлекал силы неприятеля: после нападения на Опочку литовские войска не являлись более в русских пределах, но московские входили несколько раз в Литву. В 1518 году князь Василий Шуйский с новгородскою силою и большим нарядом, а брат его, Иван Шуйский, с псковскою силою выступили в поход к Полоцку. Подошедши к городу, начали ставить туры и бить пушками стены; на помощь к ним пришел московский отряд под начальством князя Михаила Кислицы; но полочане из посада, из-за острожья сильно отбивались, и скоро в стане осаждающих сделался голод, колпак сухарей стоил алтын и больше, конский корм также вздорожал; к большему несчастию, неприятель овладел стругами, на которых отряд детей боярских переправился на другой берег Двины за добычею; преследуемые литовским воеводою Волынцем, эти дети боярские бросились назад, к Двине, но перевезтись было не на чем, и много их потонуло в реке; Шуйские принуждены были отступить от Полоцка без всякого успеха. В следующем году князь Михайло Кислица с новгородцами и псковичами пошел опять в Литву, под Молодечно и другие городки, и «вышли назад, к Смоленску, все сохранены богом», по выражению летописца. Значительнее был в том же году поход князя Василия Васильевича Шуйского от Смоленска, князя Михайла Горбатого от границ новгородских и псковских, князя Семена Курбского из страны Северской: воеводы эти ходили к Орше, Могилеву, Минску, воевали и пленили по самую Вильну. Пятеро знатнейших панов литовских вышли было к ним навстречу, но, видя поражение своих передовых полков, отступили в глубь страны; московские воеводы не преследовали их туда и возвратились к своим границам, удовольствовавшись страшным опустошением неприятельских областей. Другие воеводы ходили к Витебску и Полоцку.