Решительно подавив сопротивление Казани, Василий предпринял меры для установления дружественных отношений с другими государствами Уведомив крымского хана Менгли-Гирея о смерти Ивана III, Василий потребовал новую шертную грамоту, но крымский хан отошел от прежних договорных формул и дал грамоту, которая существенно отличалась от шерти, данной раньше отцу Василия Ивану III. Новая грамота не была принята Василием. В Москве была снята копия с прежней договорном грамоты, имя Ивана было заменено именем Василия и окольничий Константин Заболоцкий отправился в Крым для того, чтобы Менглы-Гирей подтвердил свою верность старому союзу на прежних условиях.

Желая сохранить традиционные дружественные отношения с Данией, Василий 17 июля 1506 г. послал к Датскому королю Хансу своего посла Истому с поручением добиться подтверждения договора 1493 г., по которому стороны обязались бороться против узурпатора Швеции Свена Стуре и великого Литовского князя Александра Ягеллона.

Василий просил написать такую же договорную грамоту, какая была в 1493 г. заключена между Хансом Датским и его отцом Иваном Васильевичем. Он просил короля привесить к грамоте государственную печать Дании и в присутствии своего посла Истомы поцеловать на грамоте крест. Со своей стороны он обещал по получении текста договора сделать то же самое в присутствии датских послов.

Король выполнил просьбу Василия. Датские дипломаты отыскали черновик старого договора и внесли в его текст необходимые поправки. Имя Ивана было заменено именем Василия, а имена прежних противников датского короля были заменены именами новых его врагов.

Свое согласие возобновить договор король Ханс I подтвердил особой грамотой, которую привез в Москву его посол Давид фон Коран.

Таким образом, уже в 1506 г. Василии и в отношениях с Данией добился сохранения прежнего положения.

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

25 мая 1506 г. из Вены в Москву был отправлен императорский посол Юстус Картингер. Он ехал в Москву для того, чтобы освободить из русского плена ливонских кнехтов и рыцарей. Год назад Картингер уже приезжал с той же просьбой, но Иван III категорически отказал. На этот раз император, видимо, надеялся, что новый великий князь Московский окажется более уступчивым. Однако Василий III ответил Максимилиану Габсбургу, что пленные могут быть освобождены лишь в случае, если Ливония перестанет поддерживать великое княжество Литовское и будет исправно выполнять условия существующего договора о перемирии. Тем самым Василий III дал понять императору, что Россия не изменит своего отношения к Ливонии и к стоящей за ее спиной империи, если с другой стороны не будут представлены убедительные доказательства миролюбия и дружественности.

Следует остановиться и на самом важном вопросе внешней политики России — на взаимоотношениях с Великим княжеством Литовским и Польшей. Польский король и великий князь Литовский Александр Казимирович Ягеллсн проводил тонкую и хитрую политику. Заключая враждебные Руси договоры, Александр лицемерно предлагал вечный мир; готовясь к воине с Россией, великий князь Литовский в это же самое время слал в Москву гонцов и послов по словами, исполненными дружбы и миролюбия. Первое такое посольство после вступления на великокняжеский престол Василия Ивановича прибыло в Москву 15 февраля 1506 г. Посольство возглавлял витебский наместник Юрий Глебович. Он предложил заключить «вечный мир», но насилии отказался, так как одним из основных его условий было освобождение всех русских городов из-под власти великого Литовского князя.