Годы после своей великой победы Карл посвятил реорганизации правительства Бургундии, где он заменил большинство графов и герцогов на своих сторонников, и завершению покорения Фризии. Мирного герцога Альдгисла сменил язычник по имени Гондебальд, которого великий майордом атаковал, когда тот начал убивать или изгонять миссионеров Виллиброрда и Бонифация. После того как Гондебальд был убит в бою, а все языческие святыни Фрисландии сожжены, Карл оставил страну настолько усмиренной, что в течение следующих двадцати лет не было ни одного мятежа.
В 735 году проблемы начались на юге. Герцог Эд умер, и Карл решил, что пришло время завершить включение его герцогства в государства франков. Он проехал по территории и заставил жителей засвидетельствовать ему почтение. Но их покорность была результатом одного только страха, и ничего больше, и, когда Карл вернулся домой, южане провозгласили своим герцогом Гунальда, сына Эда. Вероятно, Гунальд был бы смещен, если бы снова не подняли голову сарацины. Они выступили из Нарбонна под командованием Юсуфа, сына вождя, который командовал ими при Пуатье четырьмя годами ранее, перешли Рону и захватили древний римский город Арль. Годы 736—739-й были заняты отражением трех последовательных мусульманских вторжений в юго-восточную Галлию, и Карл настолько увяз в этой борьбе, что согласился признать Гунальда герцогом Аквитании, чтобы развязать себе руки для более серьезных дел. Наконец его старания увенчались полным успехом. Прованс был очищен от арабов, Арль и Авиньон, которые мусульмане какое-то время удерживали, возвращены. Ним, Агд и Безье, находившиеся в руках арабов после большого вторжения в Септиманию в 725 году, были взяты и сожжены, а также большая армия была уничтожена в районе Нарбонна. Но этот город пока еще не попал в руки франков. Вместе с южной половиной Септимании он оставался плацдармом сарацин, прикрывающим проходы через Восточные Пиренеи. Еще двадцать лет ему было суждено оставаться арабским. Не самому Карлу Мартеллу, а его сыну было суждено продвинуть франкскую границу до подножия гор. А тем временем сарацины Испании, присмиревшие после ударов Карла Мартелла, отказались от попыток продвижения на север и погрузились в болото гражданских войн.
Пока Карл был занят войнами с сарацинами, марионеточный король Теодорих IV, от имени которого великий майордом правил уже семнадцать лет, умер. К этому времени королевское имя уже значило так мало, что Карл даже не стал тратить время на поиски и коронацию нового наследника бездетного короля. Последние четыре года своей жизни он правил сам — без сюзерена. Правда, королевский титул он не принял и продолжал называться майордомом или герцогом франков. Его не слишком интересовали названия, пока реальная власть оставалась в его руках.
Возврат Прованса и севера Септимании был последним триумфом великого майордома. Но и последние четыре года его жизни были не лишены важных дел. В 738 году он заставил вестфальских саксов на Липпе и Эмсе отдать ему почести и выплачивать дань. В 739 году была завершена организация южногерманской церкви созданием четырех епископств в Баварии, замыкавшихся на Бонифация, к этому времени ставшего архиепископом зарейнской Германии, как на митрополита. Так Бавария стала в духовном отношении составной частью франкской церкви, так же как в политическом отношении она стала частью франкского государства. Но хотя Карл твердо поддерживал церковь в своих владениях, он не вмешивался в церковные диспуты за их пределами. Папа Григорий III затеял борьбу с королем лангобардов Лиутпрандом и предложил благочестивому правителю франков выступить против врага церкви. Карл отказался. Лиутпранд помогал ему в борьбе с сарацинами, и великий майордом вовсе не собирался нападать на своего прежнего союзника лишь потому, что у него возникли разногласия с папой относительно герцогства Сполето. Летом следующего года великий майордом почувствовал, что его здоровье начало ухудшаться, хотя ему было только пятьдесят четыре года. Он решил привести дела в порядок и собрал большой совет франков. С его согласия он стал передавать управление королевством своим сыновьям. Больше не было короля из Меровингов, права которого следовало учесть, поскольку Теодорих IV умер четырьмя годами раньше. Поэтому Карл вместе с советом распорядился землями так, словно они были законным наследством Арнульфингов. У великого майордома было три взрослых сына: Карломан и Пипин — от законной супруги Ротруды и Грифон, которого ему родила Свангильда, баварская леди, взятая им в наложницы во время баварской кампании 725 года. Им было соответственно двадцать семь, двадцать шесть и семнадцать лет. Карл передал управление Австразией и Швабией Карломану, Нейстрией и Бургундией — Пипину. Говорят, что он намеревался оставить небольшой участок на границе Нейстрии и Австразии Грифону. Два крупных вассальных герцогства, Бавария и Аквитания, не были названы при разделе, хотя первое оказалось под влиянием Карломана, а второе — Пипина.