W owych czasach najgroźniejszym wrogiem Rzymu było afrykańskie państwo Wandalów, rządzone przez Genzeryka, który już raz zdobył i splądrował Rzym latem 455 roku. Majorian zrozumiał, że jedynym wyjściem jest likwidacja barbarzyńskiego państwa Genzeryka, które okupowało najbogatszą prowincję zachodniego imperium. W tym celu przystąpił do organizowania gigantycznej floty i armii inwazyjnej. Planując przyszłą konfrontację z Wandalami, w szeregi rzymskiej armii wcielał też Hunów i wojowników innych plemion barbarzyńskich.
Kampanie w Galii i Hiszpanii Początkowo cesarz kontrolował tylko Italię. Nawet w rodzinnej prowincji cesarza, pod wpływem dążeń separatystycznych, nie chciano uznać nowego władcy. Do nielicznych wyjątków należał dawny przyjaciel Majoriana – Egidiusz. Do zajmowania nowych rzymskich terenów przystąpili Frankowie, Wizygoci i Burgundowie. Ci ostatni latem 457 zajęli nawet przy entuzjazmie rzymskiej ludności (częste zjawisko w V wieku) jedno z największych tamtejszych miast – Lugdunum (obecny Lyon). Zrywając z polityką poprzednich cesarzy, którzy nie brali bezpośredniego udziału w kampaniach wojskowych, Majorian we współpracy ze swoim sekretarzem Piotrem odbił miasto zimą 458 roku i za sprzyjanie wrogom ukarał je potrójną daniną.