Bár István immár új legitimációval bíró királya volt Magyarországnak (a korszakra jellemző szemlélet alapján azonban ő magát okleveleiben a magyarok, nem pedig Magyarország királyának nevezte), de tényleges uralma továbbra is csak a Kárpát-medence nyugati részére, vagyis a Dunántúl nagy részére és a nyugati Felvidékre terjedt ki. A térség többi pontján tőle lényegében független törzsfők gyakoroltak hatalmat. Istvánnak, ha ténylegesen minden magyar királya akart lenni, továbbá ha az általa képviselt új rendet az egész Kárpát-medencében el akarta terjeszteni, szembe kellett fordulnia e törzsi hatalmasságokkal, és fegyveres úton meg kellett fosztania önálló törzsi államuktól, avagy békés eszközökkel meghódolásra kellett bírnia őket. E program megvalósítása a koronázást követően közel három évtizedet vett igénybe.
A sort rokonával, Gyulával kezdte. A gondolatot, hogy vele le kell majd számolnia, talán már fejedelmi trónra lépte, 997 óta melengette, hiszen tudta: amíg anyai nagybátyja önálló, az övétől eltérő orientációjú ország élén áll, addig az ő főhatalma a magyar törzsek felett erősen korlátozott. Ugyanakkor abban sem lehetett biztos, hogy Gyula előbb-utóbb nem lép-e fel támadólag, immár katonai úton adva nyomatékot annak az ortodox befolyásnak, amely 985–990 táján vértelenül nyert teret a Dunántúlon. A Gyula elleni háborúnak más, de nem kisebb tétje volt, mint a Koppány elleninek. Míg ez utóbbi arról döntött, hogy ki viselje Géza halála után a nagyfejedelmi tisztet, és a főhatalom új birtokosa milyen arcélt adjon politikájának (pogányos legyen-e az, vagy a latin kereszténységet befogadó), addig a Gyulával megvívandó harcnak azt kellett tisztáznia: a latin vagy a görög rítus kerekedik-e felül a Kárpát-medencében, azaz a római kereszténység tör-e utat magának a Keleti-Kárpátokig, vagy a megerősödő görög hit terjeszti ki befolyását az Alpok keleti nyúlványaiig. A Koppánnyal való összecsapás tétje a Kárpát-medence nyugati része volt, a Gyulával történő megmérkőzésé immár a térség két szélső (nyugati és keleti) sávja.
Az István és Gyula közti háborúról egyetlen kortárs külföldi forrás tájékoztat, a Hildesheimi Évkönyv. Eszerint 1003-ban „István magyar király sereggel ment anyai nagybátyja, Gyula király ellen; miután őt feleségével és két fiával együtt elfogta, országát erőszakkal a keresztény hitre kényszerítene”. Mindenekelőtt feltűnő, hogy a német kútfő Gyulát királynak nevezte, uralmi területét pedig országnak. Ez arra a függetlenségre mutat, amit Gyula a magyar királlyal szemben élvezett, vagyis a belső értékrend alapján Gyula lényegében Istvánnal azonos rangúnak tekinthető. Nem feltétlenül téves és túlzó a kútfő keresztény hitre térítéssel kapcsolatos megjegyzése. Gyula és udvara ortodox keresztény volt, de népe körében csak nagyon lassan terjedt a görög hit, amit a fentebb már idézett, görög előképre visszamenő szláv forrás igazol. Gyula nélkülözte a másutt lekötött Bizánci Birodalom támogatását – talán mind katonai téren, mind a hittérítésben -, ezzel szemben István oldalán ott álltak Gizella kíséretének tagjai. A magyar király számára erkölcsi tőkét jelentett, hogy az egész keresztény Nyugat-Európa kiállt mellette. Hogy ez a hír német évkönyvben maradt ránk, mutatja azt az érdeklődést, amit német területen tanúsítottak István harca iránt.
A magyar források érdekesen egészítik ki a Hildesheimi Évkönyvben olvasható tudósítást. A 14. századi krónikakompozíció közvetve innen vette át a Gyula elleni háború hírét, de megtoldotta azzal, hogy Gyula „akkor egész Erdélyország kormányzását kezében tartotta”. Az biztosra vehető, hogy a gyula-törzs a honfoglaláskor nem szállta meg Erdélyt, csak valamikor a 10. század folyamán vette birtokba. Máig nem dőlt el azonban végérvényesen, hogy mi értendő Erdélyen, ahová István hadat vezetett. A hagyományos felfogás szerint Gyula hatalma az egész történeti Erdélyre kiterjedt, uralmi központja pedig Dél-Erdélyben, a Maros mentén fekvő Gyulafehérváron volt. Ezzel szemben komoly méltánylást érdemlő érvek sorolhatók fel amellett, hogy Gyula Erdélye éppen Dél-Erdélyt nem foglalta magában, hanem attól északra, a Felső-Tisza folyásától a Marosvölgyig terjedt, s központja talán Doboka környékén kereshető.
Becses információt hagyott ránk a krónika annak rögzítésével, hogy István Gyula „országát, amely igen tágas és nagyon gazdag volt, a Magyar Királysághoz csatolta”. Ezzel e kútfő a háború lényegére tapintott rá, amelyet István azért indított, hogy fennhatóságát kiterjessze Erdélyre, és ott uralomra juttassa az általa képviselt eszméket, intézményeket. Rosszul értelmezte azonban német forrását a krónika, amikor a háború okaként Gyula pogányságát említette. Mind a krónikából, mind Anonymus gesztájából kitetszik, hogy politikai ellentétek húzódtak István és Gyula között. Az előbbi szerint Gyula károkat okozott a magyaroknak (vagyis Istvánnak és alattvalóinak), az utóbbi szerint pedig Gyula „sok olyat tett, amivel szembeszállt Szent István királlyal, jóllehet anyja rokonságából való volt”. A Névtelen azt is tudni véli, hogy Gyula és két fia továbbra is birtokolhatták volna Erdélyt, ha „nem cselekedtek volna mindig a szent király ellenében”: Ezzel arra a fontos mozzanatra mutatott rá, hogy a törzsfők közül az, aki meghódolt Istvánnak, átmenthette hatalmát, aki viszont nem, az háborúval volt kénytelen szembenézni. Az István és Gyula közötti fegyveres összecsapás mikéntjéről semmi hírünk nincs. Kombináció eredményeképpen lehet arra gondolni, hogy a Gyula ellen vonuló had (egyik) vezére Doboka volt, a később Ajtony ellen győztes Csanád apja, aki ismeretlen módon rokonságban állott a magyar királlyal.
István Gyula elleni háborújának egy utózöngéje még Merseburgi Thietmar krónikájába is utat talált. Innen arról szerzünk tudomást, hogy Prokujt (ez Gyula valóságos neve), a magyar király nagybátyját István szállásterületéről elűzte, az Vitéz Boleszlávnál talált menedéket, aki a magyar-lengyel határvidéken egy várat bízott a politikai menekültre. Prokuj-Gyula felesége azonban István fogságában maradt. Amikor Gyulának a neje kiszabadítására tett erőfeszítései eredménytelenek maradtak, „ajándékul kapta meg azt unokaöccse [István] kedvességéből, jóllehet ellenségek voltak. Sohasem hallottam még másról, aki ennyire kímélte volna a legyőzötteket.” Thietmar Istvánról mondott hízelgő szavai arra mutatnak, hogy a magyar király nem ontott vért hiába, megelégedett pusztán a sikerrel. Ugyancsak nem szenvedtek komoly sérelmet Gyula fiai, Bolya és Bonyha sem, akik még az 1040-es években is szerepelnek a forrásokban. Nem tudjuk, hogy Sarolt meddig élt, így arra sem válaszolhatunk, hogy István irgalmas eljárása Gyulával és családjával szemben nem Sarolt (azaz Gyula testvére) közbenjárásának köszönhető-e. Mindenesetre 1003-ban István megvetette lábát a Kárpát-medence keleti felében, és ezzel tovább javította esélyeit, hogy a többi törzsfő ellen is a siker reményében léphet fel.
Gyula legyőzése után időrend szerint Keán következett. Ő a korai magyar történelem rejtélyes figurája, nevével csak egyetlen hazai forrásban, a 14. századi krónikakompozícióban találkozunk. Ez elmondja, hogy Gyula országának elfoglalását követően István „hadat indított Keán, a bolgárok és szlávok vezére ellen, amely népek természetes fekvésüknél fogva igen megerősített helyeken laktak. E vezért sok fáradsággal és hadiverejtékkel is nehezen fogta el, megölte.” A hagyományos felfogás e Keánban bolgár cárt keresett, akivel szemben a magyar uralkodó az 1010-es években ténylegesen hadat viselt. Mivel azonban a krónika Keánról Koppány és Gyula (vagyis belföldi ellenfelek) leverése után szól, s mert a tudósítás akként folytatódik, hogy Keán helyébe „Zoltán nevű elődjét helyezte, aki azután örökölte ezen erdélyi részeket”, indokolt arra gondolni: Keán Istvánnak a Kárpát-medencén belüli ellenfele volt, Zoltán pedig az első erdélyi vajda lehetett. Keánt a krónika is bolgárok és szlávok fejének tekintette; ugyancsak bolgár kapcsolatra utal neve, amely a török kagán méltóságnévvel egyezik.
Mindezen körülmények együttesen arra mutatnak, hogy Dél-Erdélyben, Gyulafehérvár központtal számolhatunk a 11. század elején egy eredendően bolgár származású és bolgár (bolgárszláv) alattvalók felett országló előkelővel, akinek igazi nevét nem ismerjük, csak tisztségnévből alakult Keán neve maradt ránk. Családja talán már a magyar honfoglalás előtt itt élhetett. Keán az idők múltával egyre inkább úgy viselkedhetett, mint egy magyar törzsfő, halvány nyom mutat arra, hogy már a 10. század második felében szemben állt Gézával, vagyis politikai működésének színtere a Kárpát-medence és nem a dunai Bulgária volt. Döntően szláv nyelvű alattvalói vajdának nevezhették. István, miután leverte Keánt, országát a Magyar Királysághoz csatolta, az oda helyezett ispánt pedig a helyi népesség továbbra is vajdának nevezte. Így alakulhatott ki már István idejében az erdélyi vajdaság körvonala, egyelőre a dél-erdélyi térségre korlátozódva.
Nem tudjuk, hogy mikor esett áldozatul István támadásának Keán önálló állama. Lehet, hogy egyetlen akció keretében számolt le a király Gyula és Keán országával (ez esetben a Keán elleni háború dátuma is 1003 lenne), de későbbi időpont sem teljesen kizárt. Túlságosan kései időpontra azonban nem gondolhatunk. A nagyobbik István-legendában ugyanis egy besenyő támadás kapcsán István uralma alatt levőként szerepel Gyulafehérvár, e besenyő betörés vélhető időpontja pedig 1015 tája. Keán leverése eszerint 1003 és 1015 közé tehető, de inkább ennek az időszaknak az elejére. Ezzel immár a teljes kelet-magyarországi térség István tényleges uralma alá jutott. Bár István Keánt megölte, de annak leszármazottjai utóbb mint a Kán nemzetség – Baranyában és Dél-Erdélyben birtokló – tagjai bukkannak elénk.
Az ezredforduló utáni évek gyors tempójából István továbbra sem engedett. Gyula és Keán után a nem kevésbé rejtélyes fekete magyarok következtek. A velük kapcsolatos homályt csak sűríti, hogy hazai források nem szólnak róluk, szerencsére néhány megbízható külföldi kútfő nem engedte feledésbe merülni emléküket. Ezek sorában megkülönböztetett figyelmet érdemel Querfurti Brúnó (szerzetesi nevén Bonifác), aki személyesen is találkozott velük. Ő egyik munkájában arról számol be, hogy „miután mellőztem a poroszokat, ahová az újdonsült szent, Adalbert megölése miatt igazabb indok irányított volna, nem sikeres munkával és beteg vállal kezdtem az örömhírt [az evangéliumot] vinni a fekete magyarokhoz, ahová akkoriban szálltam hajóra keleti irányban”. Brúnó hajón indult el Regensburgból 1003-ban a fekete magyarokhoz, hogy azután megszakítással egészen 1008-ig próbáljon körükben téríteni, mint maga bevallja – 1008 táján (a magyarországi térítés lezárása után) keletkezett – munkájában: lényegében eredménytelenül. A fekete magyarokat tehát a Kárpát-medencében, valahol a Duna mellett kell gyanítanunk.
Brúnó magyarországi térítő munkájának két további írott emléke maradt. A 15. századból való, tehát kései életirata szerint a magyarországi, máig azonosítatlan Prago városánál pogányok támadtak rá. A nagyobbik István-legenda pedig megőrizte annak emlékét, hogy midőn Bonifácot „Magyarország alsó részébe küldte igét hirdetni a szent király [István], kardtól sebesült meg a nyakán”. E két hír nyilván egyazon eseményre utalhat, s ugyanerre vonatkozik a magától Bonifáctól származó „beteg vállal” kifejezés is. Magyarország alsó részének említése tovább szűkíti azon kört, ahol a fekete magyarokat kereshetjük: csakis a Kárpát-medence déli területei jöhetnek így szóba.
Abban a kérdésben, hogy a baranyai vagy a Marostól délre eső Dunaszakaszra gondoljunk-e (ez utóbbi egyébként Ajtony törzsi államának területe), bizton eligazít Querfurti Brúnó egy másik híradása. II. Henrik német királyhoz 1008-1009 fordulója táján vagy 1009 elején írott levelében elmondja, hogy a poroszokhoz készül, s ezt követően szól arról: „Hallottam a fekete magyarokról is, akikhez Szent Péter első követsége ment – amely sohasem jár hiába –, hogy megtérve kereszténnyé lettek, jóllehet a mieink – Isten bocsássa meg ezt – némelyeket nagy bűnnel megvakítottak.” Minthogy Ajtony területén csak 1030-ban létesült püspökség a frissen megtérített keresztények hitéletének gondozására, ezzel szemben Pécsett már 1009-ben, erősen valószínű, hogy a fekete magyarok a baranyai (és alkalmasint a folyó másik partját jelentő bodrogi) Duna-szakasz mentén éltek. További támpont, hogy a pécsi püspökség 1009. augusztus 23-ai dátummal ránk maradt alapítólevele szól Azo püspök, pápai követ közreműködéséről ennél az aktusnál. Ez lehetett Szent Péter „első követsége”, amelyről Brúnó említést tett.
Mindebből arra kell következtetnünk, hogy a fekete magyarok – a megvakításokból következően erőszakot sem nélkülöző – megtérítése 1008 folyamán történt, azt követően, hogy Querfurti Brúnó eltávozott tőlük, és azt megelőzően, hogy a poroszokhoz ment volna, ahol – mestere, Adalbert sorsában osztozva – 1009. március 9-én vértanúhalált halt. A kortárs Ademarus Cabannensis egyrészt azt jegyezte fel, hogy Fekete Magyarország onnan kapta nevét, mivel ott „a nép sötét színű az etiópokhoz hasonlóan”, másrészt pedig azt, hogy „István, Magyarország királya háborúval támadta meg Fekete Magyarországot, kiérdemelte részint erővel, részint pedig félelem és szeretet révén azt az egész földet az igazság hitére téríteni”. Újból István volt tehát a kezdeményező fél, és ezúttal a fekete magyarokkal bonyolódott háborúba. Az elmondottak alapján erre a katonai akcióra 1008-ban került sor.
A fekete magyarok – bőrük sötét színéből, továbbá határ menti lakhelyükből adódóan – nagy valószínűség szerint a 9. században a magyarokhoz csatlakozott kavarok utódai voltak (többségükben kálizok), akik bőr és hajszín szempontjából valóban elütöttek a tulajdonképpeni (e forrásban fehérnek mondott) magyaroktól. Mint a katonai segédnéphez tartozó alávetetteknek az egész Kárpát-medencében körös-körül el kellett látniuk a határvédelmet. Ebből következően nemcsak itt éltek, hanem másutt is, de Baranyában kiváltképpen népes és erős csoportjaik lehettek. A pécsi püspökség területén a későbbi századokban is többször találkozunk jelentős számú keleti népekkel. Ezek közül a böszörménynek mondottak izmaelita, vagyis muszlim hitű kálizok voltak, a besenyők és a székelyek pedig pogányok.
A fekete magyarok megtérítése jól mutatja azt, hogy kart karba öltve haladt a királyi haderő és a térítést végző papság. A lovag nyomába a pap lépett. E háború eredményeként Délkelet-Dunántúl is a magyar uralkodó tényleges fennhatósága alá jutott. Istvánnak a 11. század első évtizedében lebonyolított három belháborúja (Gyula, Keán és a Dráva-torkolathoz közeli fekete magyarok ellen) megszilárdította pozícióit a Kárpát-medence két szélén, a Dunántúlon és Erdélyben, a következő időszakra várt az a feladat, hogy a két térség közti nagy területet is betagolja a Magyar Királyságba.
A kavarok egy másik jelentős csoportja Észak-Magyarországon, a Mátra vidékén élt. Az egyetlen törzzsé szervezett kavarság fejedelme, Aba Sámuel is itt székelt. Ő – mivel családja a hajdani kazár arisztokráciába tartozott – bizonnyal zsidó vallású volt, alattvalói között itt is az iszlám követőivel és pogányokkal számolhatunk. István Aba Sámuellel nem vívott háborút, hanem megnyeréséhez diplomáciai eszközöket vett igénybe: talán 1010 táján (vagy kevéssel ezt megelőzően) egyik húgát feleségül adta Sámuelhez. E frigy feltétele az volt, hogy leendő sógora térjen át a keresztény hitre, aminek a kavar törzsfő eleget tett, és így a házasság létrejött. István utóbb Sámuelt magas udvari méltóságra emelte, a német mintára létrehozott palotagrófi méltóságot ruházta rá, ami a későbbi nádori tisztség előképe volt. Sámuel egyelőre igyekezett palástolni igazi érzelmeit, Abasáron bencés monostort is alapított, de sógora halála után trónra kerülve az István által megalkotott új rend szétbomlasztásán fáradozott. Mindenesetre az ország e részét a belháború elkerülte, éppen azért, mert Aba Sámuel meghódolt Istvánnak.
Hasonló tételezhető fel a Körösök vidékén honos törzsfő, Vata esetében is. Az ő törzsi államában 1020 tájától folyhatott térítés, bár igazán nagy lendületről itt éppen a háború elmaradása, a békés megegyezés miatt aligha lehetett szó, akárcsak Aba Sámuel területén. Vata szintén felvette a kereszténységet, hiszen róla akkor, amikor 1046-ban pogánylázadás élére állt, megtudjuk: keresztény hitről hajolt vissza a pogányságba. Vagyis Vata – Sámuelhez hasonlóan – alávethette magát Istvánnak, és kitért a fegyveres összecsapás elől. Aligha véletlen, hogy mindkét törzsfő, akikkel a magyar király békésen kiegyezett, utóbb hátat fordított a kereszténységnek meg István új rendjének, és a pogány restauráció élére állt. A velük kötött megállapodással tehát – akkor úgy tűnt – István járt jobban, az ő akarata érvényesült, de a végső elszámolásnál kiderült, hogy csak időt nyert, hiszen a Sámuellel és Vatával megvívandó háborúk későbbre és másokra maradtak.
Az 1020-as évek végére egyetlen törzsfő maradt, aki még önálló országgal rendelkezett a Kárpát-medencében, a Maros-vidéki Ajtony. A 11. század elejének törzsi vezetői közül – a nagyobbik Gellért-legenda jóvoltából – Ajtonyról tudjuk a legtöbbet. E forrásban a következőket olvashatjuk róla: „Volt akkoriban Marosvárott egy roppant hatalmú, Ajtony nevű fejedelem, aki Bodony [Vidin] városában a görög rítus szerint vette fel a keresztséget. Igencsak nagyra volt tulajdon erejével és hatalmával. Hét feleséget is tartott, merthogy a keresztény hitben nem volt éppen tökéletes. István királynak pedig a legkevésbé sem adta meg a tiszteletet, annyira bízott ama harcosok és nemes emberek sokaságában, akik fölött uralmat gyakorolt. Szilaj lovainak se szeri, se száma nem volt, azokról nem is beszélve itt, amelyekre a lovászok gondozásában a házak táján vigyáztak. Barmokkal is végtelen számban rendelkezett, minden csordát egy-egy gulyás keze alá adva, s voltak azonfelül uradalmai és udvarházai is, de még a királynak a Maroson leúsztatott sója fölött is bitorolta a hatalmat, amikor a folyó révjeiben végig a Tiszáig vámszedőket és őröket helyezett el, s nem hagyott kisiklani semmit a vámoltatás alól. A görögöktől pedig felhatalmazást szerzett, majd az említett Marosvárott kolostort emelt Keresztelő Szent János tiszteletére, amelybe apátot tett görög szerzetesekkel együtt a maguk rendszabálya és szertartása szerint. S minthogy a föld e férfiút szolgálta a Körös folyótól egészen az erdélyi részekig, illetve egész Bodonyig és Szörényig, amelyet végig mindenestül a maga hatalma alatt tartott, ezért fölényben volt a fegyveresek sokaságát illetően, a királlyal pedig a legkevésbé sem törődött.” Ajtony tehát Bizánc felé tájékozódott, de ortodox rítusú püspökség alapításáig nem jutott el. A görög hitet nem őszinte meggyőződésből, hanem politikai számításból vette fel, szíve mélyen nyilván megmaradt pogány nagyúrnak. Hatalmának alapja – nomád tömegek felett uralkodó törzsfőhöz illően – óriási állatállománya volt. A neki engedelmeskedő nép – amint erre a nagyobbik István-legenda halványan céloz – pogánynak tekinthető.
Hosszas viták után a szakirodalomban ma már nagyjából uralomra jutott az a nézet, hogy István Ajtony elleni háborúját közvetlenül az 1030 előtti évek egyikében, talán 1028 táján indította, mivel 1030-ban Ajtony területén létrejött a marosvári (csanádi) püspökség. Több körülménnyel függ össze, hogy miért „várt” István mintegy negyedszázadot Gyula vagy Keán leverése után Ajtony országa felszámolásával. Egyrészt volt egy olyan hosszas időszak, amikor mind István, mind Ajtony szövetségesi viszonyt ápolt a görög császárral. II. Baszileiosz bizánci uralkodónak sem lehetett ez ellenére, hiszen maga sem tudhatta, hogy – ha majd sor kerül összecsapásukra – melyikük kerekedik a másik fölé. Másrészt Ajtony olyan hatalmas erővel rendelkezett, hogy Istvánnak türelemmel ki kellett várnia a megfelelő időpontot. A konkrét apropót, hogy István miért éppen akkor indította el seregét, amikor elindította (mert természetesen ezúttal is a magyar király volt a támadó fél), nem ismerjük, de nyilván szerepe volt ebben a Bizánci Birodalmat évszázadok óta nem tapasztalt csúcspontra emelő II. Baszileiosz 1025-ben bekövetkezett halálának. Ezt követően a keleti császárság gyors hanyatlásnak indult, s Istvánnak nem kellett attól tartania, hogy Bizánc beavatkozik Ajtony oldalán az ő háborújukba. Számításaiban nem is csalatkozott, hiszen Bizánc kívül maradt ellentétük erővonalán.
Magáról a háborúról részletes ismereteink vannak. A királyi sereget bizonyosan nem István vezette (akkor már 50. életéve felé tartott), hanem rokona, Csanád. A kiegyenlített erőviszonyokra utal, hogy az első ütközet Ajtony sikerével ért véget, majd a következő napon – a Gellértlegenda szerint „mennyei segítséggel”, Szent György támogatásával – Csanád döntő győzelmet aratott, „Ajtonyt pedig Csanád serege a csatatéren megölte”.
István, aki fiatalon kezdte a háborúskodást (hiszen Koppány legyőzésekor alig 16–17 éves volt), 30 évi hosszú menetelés után célba ért. Nem véletlenül írta fiának, Imre hercegnek az Intelmekben (bizonyosan még az Ajtony elleni háborút megelőzően), hogy „nem volt részed sem a hadjáratok fáradalmaiban, sem a pogányok különféle támadásaiban, amelyek közepette nekem szinte az egész életem őrlődött”. A cél pedig, amit István Ajtony országának felszámolásával elért, nem volt kisebb, mint az, hogy immár az egész Kárpát-medence felett teljhatalmat gyakorló uralkodóvá váljék. Ha a korábbiakban csak bizonyos megszorítással beszéltünk Magyarországról, ettől kezdődően politikai realitásként szólhatunk róla. István három évtizedes háborúskodással, illetve ügyes kompromisszumokkal felszámolta a törzsfők önállóságát, uralmát kiterjesztette a teljes Kárpát-medencére, és ezzel megteremtette Magyarországot.