Быстрота и предприимчивость, свойственные прежней политике Альбрехта, сменились стремительной погоней за дешевыми надеждами и безрассудными планами. Великий магистр побывал в Праге и Вене, Венгрии и Силезии, Саксонии и Бранденбурге. Вскоре, вознамерившись заработать денег, он решил поступить на службу к папе или вообще к королю Франции, потом ввязался в авантюру с датским королем. Осенью 1522 года и весной 1523 года он принимал участие в рейхстагах в Нюрнберге. Эта бурная деятельность велась уже не ради ордена. Великим магистром овладело глубокое беспокойство, у него начался внутренний кризис. Но это беспокойство, эта стремительность действий, которыми сопровождались победы и провалы больших и малых планов, постепенно уступали место чему-то новому, чему впоследствии суждено было определять его поступки и всю его жизнь. Вопросы, которые целых десять лет не давали покоя Альбрехту, разрешились не вдруг, не под воздействием какого-то сиюминутного чувства, а в результате длительных размышлений, благодаря окрепшей в нем вере. Его жизнь обрела новый смысл, когда он познакомился с учением Мартина Лютера. Теперь он создал свой собственный образ государства и по-новому определял для себя обязанности правителя. Утвердившись в новой вере, он обрел и внутреннее спокойствие, которого старая вера ему дать не могла; лишь тогда он нашел в себе силы и мужество порвать со старым и в своем государстве, отказавшись от орденской политики последних десятилетий, ибо новое содержание, основанное на учении Мартина Лютера, которое захватило старые орденские земли, требовало и новой формы.
В 1522 году, принимая участие в рейхстаге в Нюрнберге, великий магистр увидел, какой богатой духовной жизнью живут местные горожане, и понял, что нужно было Пруссии. Однако куда важнее для него была встреча с нюрнбергским реформатором Осиандером, проповеди которого произвели на него глубочайшее впечатление. Он начал склоняться к учению Мартина Лютера. Вначале, уступая требованиям своей политической деятельности, он не решался принять его полностью. Но кроме политических, у великого магистра были и духовные обязанности перед орденом. Вопрос о реформе ордена, возникший еще в XV веке, сейчас был актуален как никогда. Папская курия тоже нуждалась в некотором обновлении. Так не логично ли было поручить решение этого вопроса тому, в ком жил истинный дух реформации? Уже осенью 1521 года среди братьев родилась мысль послать орденские статуты Мартину Лютеру, чтобы тот высказал о них свое суждение. Однако этот план так и не был осуществлен.
Зоркий глаз непременно заметил бы, что в великом магистре произошла некоторая перемена. Папа недоверчиво наблюдал за его поведением; по курии ходили слухи, что Альбрехт принял новое учение. В конце 1522 года Лютер уже знал об этом: «Говорят, он не должен дурно думать о Евангелии». Летом следующего года великий магистр решил сам тайно разыскать реформатора. Речь по-прежнему шла не о роспуске ордена, а о его реформировании — начиная с руководства и заканчивая рядовыми членами. Осенью 1523 года Альбрехт Бранденбургский и Мартин Лютер встретились. По пути из Берлина в Нюрнберг Альбрехт, сделав крюк, заехал в Виттенберг, где искал Лютера. Альбрехт снова предложил реформатору заняться усовершенствованием правил ордена. В ответ Лютер, как сам он позднее рассказывал, посоветовал ему забыть эти бессмысленные и глупые правила, взять себе жену и установить в прусских землях ордена политическую власть, превратив их в княжество или герцогство. Более подробно Лютер изложил свое отношение к Немецкому ордену в послании «К господам Немецкого ордена, о том, что надлежит им избегать ложного целомудрия и стремиться лишь к истинному целомудрию в супружеской жизни». Он предлагал отменить целибат и секуляризовать орденское государство, а братьев назначить на светские должности; так они могли бы «с христианским смыслом и с одобрения подданных» сохранить во владении Пруссию.
Реформатор обозначил главную задачу. Еще столетие назад Генрих фон Плауэн попытался по-новому выстроить отношения между орденом и государством, но прежде сословия повлияли на характер государства «снизу» и «изнутри»; теперь же оставался лишь завершающий штрих: изменить саму форму власти и установить тем самым новые, рациональные отношения между сувереном и подданными, между правительством и народом. Лишь тогда власть вновь обретет свое право и свою истинное назначение.
