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