Przeciw Rzymowi W 80 p.n.e., na wezwanie Luzytanów, powrócił na Półwysep Iberyjski, gdzie stanął na czele powstania przeciw władzom rzymskim. Wkrótce siły Sertoriusza, wzmocnione uchodzącymi z Italii przeciwnikami Sulli, głównie popularami, opanowały znaczną część Hiszpanii.
Dla samej Hiszpanii wojna ta miała większe znaczenie niż dla Rzymu. Opierając się na miejscowej ludności, wśród której cieszył się wielką popularnością, Sertoriusz próbował stworzyć niezależne od Rzymu państwo ze stolicą w Osca (obecnie Huesca). Powołał nawet senat konkurencyjny wobec rzymskiego. Zdaniem niektórych historyków państwo to miało być tylko odskocznią do dalszej walki o Rzym. Podstawą siły Sertoriusza stał się nowy stosunek do ludności prowincjonalnej. Sertoriusz starał się o względy miejscowej ludności, którą traktował jako sojuszników, zmniejszając podatki, szanując jej zwyczaje i religię, nie obciążając utrzymaniem wojsk. Jednocześnie próbował przekonać miejscową arystokrację do przyjęcia rzymskiej kultury, wprowadzając nauczanie łaciny i podstaw rzymskiej cywilizacji dla ich synów, zapewniając im wykształcenie i wyszkolenie wojskowe na wzór rzymski (w tym celu powołał specjalną szkołę). W oparciu o tak przygotowaną ludność iberyjską utworzył silną armię, z którą Rzymianie długo nie mogli sobie poradzić.