С 1466 г. по 1657 гг. Восточная Пруссия была вассалом Польского королевства. Вассалитет не совсем есть факт вхождения в состав страны, скорее - некоторые ограничения во внешней политике. Так в 1525 году великий магистр Тевтонского ордена Альбрехт Гогенцоллерн из династии Бранденбургских Гогенцоллернов перешёл в протестантизм, сложил с себя полномочия великого магистра и объявил о секуляризации прусских земель. Новообразованное герцогство Пруссия стало первым протестантским государством в Европе.
В 1466 году по Второму Торуньскому мирному договору Тевтонский орден вынужден был признать себя вассалом польского короля.
В герцогстве Пруссия установилась династия Гогенцоллернов, к которой принадлежал Альбрехт I. Его преемник Альбрехт II Фридрих (1568—1618) страдал слабоумием и поэтому Польша в 1577 году назначила собственных администраторов герцогства, которыми с 1603 года были курфюрсты Бранденбурга. После смерти Альбрехта II Фридриха в 1618 году курфюрсты Бранденбурга, которые тоже принадлежали к династии Гогенцоллернов, унаследовали титул прусских герцогов, однако Пруссия по-прежнему считалась вассалом Речи Посполитой.
Лишь в 1657 году, воспользовавшись тяжёлым положением Польши в войнах со Швецией, Русским царством и запорожскими казаками, Бранденбург добился подписания Велявско-Быдгощского трактата с Польшей, по которому герцогство Пруссия становилось независимым и примыкало к Бранденбургу. В 1701 году с провозглашением Королевства Пруссия состоялось окончательное объединение Пруссии и Бранденбурга.