Согласно Ионе и Псевдо-Фредегарию, виновницей изгнания Колумбана была королева Брунхильда, ненавидевшая святого. В источниках VII в. королева изображена как жестокая и властолюбивая женщина, «новая Иезавель». Такое отношение к Брунхильде отчасти объяснялось её вестготским происхождением, отчасти – её попытками удержать власть над Бургундией. Назначая королей из числа своих детей и внуков, Брунхильда препятствовала браку Теодориха II, т.к. опасалась утратить влияние на юного короля. По свидетельству Псевдо-Фредегария, в 606 или 607 г. она расстроила брак Теодориха II и вестготской принцессы Эрменберги, которую пришлось вернуть в Испанию. Королева самовольно распоряжалась епископскими кафедрами и способствовала симонии, приказала убить св. Дезидерия, который, подобно Колумбану, критиковал личную жизнь Теодориха II. В письме Булгара, графа Септимании (около 610 г.), Брунхильда названа коварной интриганкой и вдохновительницей раздоров. В 613 г. Хлотарь II, объединивший франкские королевства, жестоко расправился с Брунхильдой и уничтожил почти всех её потомков. Более поздние авторы, пытаясь оправдать действия Хлотаря II, подчёркивали, что постигшая Брунхильду кара была заслуженной: из-за грехов королевы проклятие постигло всех членов её семьи. В то же время подозрения Брунхильды и Теодориха II относительно Колумбана могли иметь основание. Франкские правители враждовали между собой, поэтому Колумбан, лишившись благосклонности Теодориха II, мог рассчитывать на сочувствие Хлотаря II и короля Австразии Теодеберта II (596–612 гг.). В 610 г., когда Колумбан был изгнан из Луксовия, отношения между королями Бургундии и Австразии окончательно испортились: Теодеберт II заставил брата вернуть земли, ранее относившиеся к Австразии, но присоединённые к Бургундии по условиям раздела 596 г. После этого оскорблённый Теодорих II начал готовиться к военным действиям. Колумбан прибыл к Хлотарю II, который радушно встретил святого и принял во внимание его совет не вмешиваться в междоусобицу. Достигнув Австразии, Колумбан познакомился с влиятельными аристократами Хагнериком и Аутарием. Их дети впоследствии стали монахами и внесли значительный вклад в распространение монашеских обычаев Колумбана. По мнению исследователей, в Меттисе (ныне Мец) Колумбан встретился с королём Теодебертом II и монахами, покинувшими Луксовий. Король предложил святому поселиться в его владениях и проповедовать язычникам, посоветовав найти место для основания монастыря на юго-восточной окраине Австразии, граничившей с языческой Алеманнией. Исследователи полагают, что Теодеберт II, впечатлённый успехами римской миссии в англосаксонской Британии, также намеревался послать проповедников к соседним языческим народам. Святой в сопровождении учеников отправился вверх по течению Рейна. Весной или летом 611 г. он прибыл к Боденскому озеру и поселился в уединённой келье близ города Бриганций (ныне Брегенц). Согласно Ионе, святому не понравилась местность, но он решил остаться на время, чтобы проповедовать язычникам-свевам. Обнаружив, что они собираются принести жертву богу Водану, Колумбан подул на приготовленную для этого бочку с пивом, которая сразу же развалилась на куски. После этого некоторые язычники приняли крещение, а отступившие от христианства вернулись к истинной вере.