Официальные дипломатические отношения между Московским царством и Пруссией начались в 1516 году при великом князе Василии III. Тогда в Москву для заключения союза против Польши от Великого магистра Тевтонского ордена прибывает посол Альбрехт. Отношения с Орденом существовали и ранее, однако только при Альбрехте происходит преобразование Ордена в светское государство – Герцогство Пруссия.
1516. НАЧАЛО ДИПЛОМАТИЧЕСКИХЪ СНОШЕНІЙ МОСКОВСКАГО ПРАВИТЕЛЬСТВА СЪ ВЕЛИКИМЪ МАГИСТРОМЪ ОРДЕНА ВЪ ПРУССИИ, АЛЬБРЕХТОМЪ, МАРКГРАФОМЪ БРАНДЕНБУРГСКИМЪ (л. 1).

Лѣта 7024, пріѣхалъ къ великому князю отъ Максимиліана Алексѣй Заболотсвой да діакъ Олексѣй Малой; а ѣхали на маистра Пруского землю, да были у маистра Пруского. И маистръ имъ говорилъ, чтобъ велики го?сударь меня жаловалъ и берегъ и во единачствѣ меня учинилъ съ собою, а язъ о томъ хочю слати въ великому государю своего человѣва Шимборка.

И князь велики послалъ къ Максиміану діака своего Васильа Тетерина, а поѣхалъ Василей на маистрову Пруского землю. И князь велики приказалъ къ маистру что его жаловати и беречи хочетъ, а онъ бы прислалъ къ нему своего человѣва бити челомъ, и какъ будетъ пригожъ, и язъ его во единачствѣ съ собою учиню.

А что съ Васильемъ къ маистру о томъ наказано, и то писано въ Максимьановыхъ книгахъ подлинно.

И Василій Тетеринъ отъ Максимьяна пріѣхалъ, а сказалъ великому кннзю, что маистръ государского жалованьа хочетъ, а шлетъ къ нему ІІІымборка же.

Цит. по: Памятники дипломатических сношений Московского государства с Немецким Орденом в Пруссии (годы с 1516 по 1520). Том издан под наблюдением Г. Ф. Карпова (Сборник Императорского Русского исторического общества. Вып. 53.СПб.,1886.)