В январе 1525 года по поводу своего знакомства с одним из этих художников Денк сам был вызван в городской Совет, и отцы города подвергли директора школы особо пристрастному допросу. В течение месяца Совет выяснял его взгляды по самым различным религиозным вопросам. С самого начала отцам города казалось, что ответы Денка несколько уклончивы, а после того, как он изложил им свое понимание евхаристии, их подозрения утвердились окончательно. Не отрицая физического пресуществления Христа в хлебе и вине евхаристии, он отметил, что главный вопрос на самом деле заключается в том, имеет ли человек, причастившийся хлебом и вином, живую и личную веру. Такой ответ их явно не удовлетворил и 21 января 1525 года, в день первого крещения анабаптистов в Цюрихе, Денк был навсегда изгнан из города под угрозой казни. Имущество его было конфисковано по решению Совета, якобы в пользу жены и детей.
Большую часть 1525 года Денк провел в странствиях по Германии. Он бывал с Мюнцером в Мальхаузене и посещал со швейцарскими братьями и сторонниками Цвингли город Санкт-Галлен. Осенью того же года он отправляется в Аугсбург, где снова занимается преподаванием. Однако и здесь через год местный пастор, приверженец Лютера, обрушивается с нападками на религиозные взгляды Денка, жизнь которого становится невыносимой, и в ноябре 1526 года Денк покидает город. Во время своего пребывания в Аугсбурге Балта-зар Губмайер убедил Денка принять крещение истинно верующего. Нет свидетельств, что он входил в анабаптистское братство, но он, несомненно способствовал повышению интереса к анабаптизму со стороны многих людей. После его отъезда из Аугсбурга в городе было учреждено братство. К его деятельности в период пребывания в Аугсбурге следует также отнести и крещение одного из самых убежденных анабаптистских миссионеров - Ганса Гута.
Из Аугсбурга Денк направляется в 'Страсбург, город, славящийся своей веротерпимостью, в котором многие анабаптисты нашли убежище от преследований. Однако через месяц он активно включается в религиозную полемику не только с Капито и Буцером, местными лидерами Реформации, но также и с Михелем Саттлером. На Рождество 1526 года он оставляет Страсбург и отправляется вниз по Рейну, беседуя о вере с местными пасторами и проповедуя в народе. Он даже пытается, впрочем безуспешно, обратить в христианство нескольких евреев. В феврале 1527 года Денк прибывает в Вормс, где вместе с Людвигом Хетцером работает над первым переводом на немецкий язык книг ветхозаветных пророков. В то же самое время он столь горячо обсуждал свою веру с другими людьми, что реформатские вожди в Страсбурге и Базеле весьма встревожились. В результате курфюрст палатината /пфальцграфства/ принял суровые меры против вормских радикалов, и Денк снова отправляется в странствия.
В августе 1527 года он возвращается в Аугсбург, где уже образовалось анабаптистское братство. Здесь он встречает своего крестника Ганса Гута, а также тех, с кем участвовал в религиозных дискуссиях. Эту встречу иногда называют "Синодом мучеников", потому что многие присутствовавшие на ней вскоре нашли мученическую смерть. Судя по всему, дискуссия, в основном, шла о значении "последних времен" в евангельской проповеди анабаптистов. Гут обещал в своих миссионерских проповедях не придавать чрезмерного значения скорому возвращению Христа во втором пришествии и Страшному суду, во что он искренне верил. В сентябре Денк находится в Ульме, откуда направляется в Базель. Он до крайности измучен скитальческой жизнью и пишет письмо базельскому реформату Эколампадиусу, умоляя его о разрешении поселиться в этом городе. Эколампадиусу же нужно получить от Денка письменное свидетельство, в котором бы он отрекался от своих анабаптистских взглядов, и Денк вручает ему письменное изложение своих религиозных убеждений, через два года опубликованное Эколампадиусом. Но это не было публичным покаянием, как называл его базельский реформат. Денк не изменил своей позиции. Но он был уязвлен остротой разногласий между виднейшими реформатами и анабаптистами, и хотел найти путь к примирению. Денк оставался в Базеле до своей смерти, последовавшей в ноябре 1527 года от чумы.