С 774 по 799 год Карл вел войну с народом саксов, исповедующих язычество, чьи земли простирались к востоку от Рейна и к северу от Гессена и Тюрингии. Франки всегда были для них беспокойными соседями, и еще в 758 году Саксония стала платить дань Пипину III. Историки не считают, что первое столкновение Карла с Саксонией (772 год) случилось в результате провокации. Камнем преткновения явилось язычество саксов. Основным событием войны стало уничтожение грандиозного языческого святилища, где стояла статуя Ирминсула - священнейшего кумира народа. Саксы ответили на это нападением на Гессен, воспользовавшись отсутствием короля. Но по возвращении в 775 году из Италии Карл возобновил завоевание Саксонии, которое закончилось только во время его четырнадцатого похода. Сакские племена были разрозненны и очень сильно уступали франкам во владении военным искусством и вооружении, но природные укрепления их земель: холмистая местность, горы, глухие непроходимые леса в Тевтобурге и Гарце, реки Везер и Эльба с их многочисленными притоками служили прекрасными естественными преградами и затрудняли быстрое продвижение франков в глубь страны или отступление. Войско франков было способно вести военные действия только в летнее время, и очень сложно оказалось укомплектовать гарнизоны для размещения на завоеванной территории. Когда саксы подвергались нападению, то они сдавались без сопротивления, но стоило франкскому королю вывести свои войска, как повсеместно вспыхивали восстания. Карл не облегчил положения, когда настоял на том, чтобы жители всех сдавшихся территорий приняли христианство. Главным врагом Карла был глава Вестфалии Видукинд, который в 778 году переправился с восточного берега Рейна и направился вверх по течению к Кобленцу, а в 782 году разбил карательный отряд франков в Саксонии. Очередная выходка Видукинда вызвала жестокую месть Карла. В битве при Вердене в один день оказалось убито не менее четырех с половиной тысяч саксов. В 785 году Видукинд сдался франкам на их условиях, и его народ был окрещен после того, как Карл перезимовал в Саксонии и в течение нескольких месяцев подвергал завоеванные земли разграблению. После этого на несколько лет основными центрами сопротивления стали земли на левом берегу Нижней Эльбы и в Нордальбингии (Шлезвиг). По отношению к этим землям в 799 и 804 годах Карл применил политику изгнания населения, переселяя участвовавших и не участвовавших в войне мирных жителей в другие части своей империи. Карл издал не один закон, касающийся завоеванных земель. Его Capitulatio de Partibus Saxoniae (Саксонский капитулярий, возможно, 785 года) назначал самые жестокие наказания, выносившиеся идолопоклонникам и тем, кто шел против церкви и священнослужителей. Капитулярий также обязывал все население завоеванных земель платить десятину церкви. Новый Саксонский капитулярий 797 года, изданный после совещания с представителями Саксонии, вносит некоторые изменения в основное право народа саксов, приводя его в соответствие с франкским законодательством. Это основное право было зафиксировано в Законе Саксонии, но время этого события не установлено. В Саксонии Карл основал несколько епархий: в Мюнстере, Миндене, Оснабрюке, Падерборне и Бремене. Во главе каждой из них стоял выбранный Карлом из местной знати граф, который по требованию императора проводил слушания в судах, согласно франкскому законодательству. Карл обязал священнослужителей докладывать ему о тех округах, в которых неправильно вершилось правосудие. В 797 году или раньше Карл стал выделять так называемых государевых посланцев - миссий - из своего ближнего окружения для выполнения специальных поручений. Они разъезжали по стране и контролировали местных управляющих. Народные собрания в Саксонии обладали законной силой лишь в том случае, если они были созваны официальными представителями императора. При такой системе управления после 804 года в Саксонии установилось спокойствие. В IX веке саксы, сохраняя большую часть своего примитивного законодательства и культуры, стали истинными христианами и полностью смирились с франкским правлением.
Бавария была аннексирована Карлом с меньшими трудностями и немного раньше, чем Саксония. Тассилон, последний герцог Баварии из династии Агилольфингов, получил герцогство в 748 году из рук Пипина III, которому принес клятву верности, но так ни разу и не появился ни на одном ежегодном собрании и не принял участия ни в одной из кампаний Пипина, а затем Карла. Под давлением короля Тассилон принес еще одну присягу в 781 году, а затем и в 787 году, но во второй раз он дал клятву, только когда войско франков приблизилось к границе Баварии. На сейме 788 года он был осужден по подозрению в заговоре с аварами. Жизнь ему сохранили, но отправили в монастырь, а Бавария была разделена между франкскими графами. В IX веке баварцы стали основной силой, поддерживавшей восточнофранкскую монархию, а Регенсбург стал главной резиденцией Людовика Немецкого. Одновременно с Баварией Карл получил беспокойных соседей в лице аваров, которые кочевали по венгерским степям с 568 года. В 791 году он совершил набег на их западные земли, лежавшие между реками Энс и Раба. Укрепленный лагерь (ринг) аварского хана был разграблен в 795 году маркграфом Эриком Фриульским и полностью уничтожен Пипином, вторым сыном Карла, в 796 году. После этого события авары послали в Ахен нескольких своих предводителей, которые заключили мир с императором и приняли христианство. На епископа Арна из Зальцбурга была возложена задача обратить аваров в христианство. В 805 году хан, почувствовав угрозу безопасности для своих племен со стороны славян, принял христианскую веру и признал императора своим покровителем.
Более успешной, но менее значительной в историческом масштабе, чем экспансия франков на востоке, была кампания, во время которой Карл со своей армией воевал с арабами на севере Испании. В 778 году Карл сам командовал экспедицией против Сарагоссы. Она окончилась неудачей, так как Карл не получил ожидаемой поддержки от восставших эмиров. Во время отступления через Пиренеи арьергард франков был уничтожен, но не арабами, а басками - христианами из Памплоны, у которых он вызвал праведный гнев, разрушив стены их города. Эйнгард, биограф Карла, считает это событие незначительным, но судьба маркграфа Роланда, префекта Бретонской марки, который пал в Ронсевальском ущелье с другими известными воинами (15 августа 778 года), вошла в легенды и песни. Чтобы восстановить отношения с испанскими христианами, Карл встал на их сторону во время спора по вопросу адоптианства, когда они признали архиепископа Толедо еретиком. Карл хотел провести границу Франкского государства на южном склоне Пиренеев как внешнее укрепление городов Нарбонна и Септимании. И он преуспел. В 801 году сыном Карла Людовиком была захвачена Барселона. В этом ему помогал граф Вильгельм Тулузский, герой, чье имя, подобно имени Роланда, увековечено в средневековом эпосе. В 807 году Памплона признала покровительство Карла и стала вторым бастионом Испанской марки, пограничной области государства Карла, и защищала подход к Пиренеям как с запада, так и с востока.