Az egyházszervezet megteremtése a legszorosabban összekapcsolódott a vármegyék (várispánságok) életre keltésével (várak építése, átalakítása, ispánok állítása, a feladatkörök meghatározása), és a király példátlan aktivitása mindkét vonatkozásban meghatározó jelentőségű volt. A világi igazgatási egységek szolgáltak keretül a püspökségek megszületéséhez és egymástól való elhatárolódásukhoz. A legkorábbi, székhelyhez kötött, latin rítusú püspökség a veszprémi volt. 1009. évi adománylevele területét négy vár (Veszprém, Fehérvár, Kolon és Visegrád) megyéjével azonosította. Felállítását már a nagyobbik István-legenda kapcsolatba hozta István bajor feleségével, hiszen azt írta, hogy Gizella a veszprémi püspöki egyházat alapkövétől kezdve sok mindennel felruházta. Egy 1232. évi oklevél pedig egyértelműen Gizellához kapcsolta alapítását. Ugyanezt a gyanút erősíti az a körülmény, hogy a mindenkori veszprémi püspököt illette meg a magyar királynék megkoronázásának joga. A veszprémi püspökség közvetlenül a pannonhalmi apátság alapítása után, 997 körül alakult meg. Szent Mihály templomcíme aligha bajor eredetű, ott ugyanis az arkangyalnak nem volt különleges kultusza, szemben a bizánci egyházzal. Ezért felvetődhet, hogy a patrocínium Sarolt idejére mehet vissza, aki ortodox hitű volt, és Veszprémben tartotta szállását.
Veszprém püspökségének elsődlegessége Esztergommal szemben földrajzi szempont alapján is igazolható. A veszprémi püspökség északkelet-délnyugat irányban az egész Dunántúlt átfogta. Ezzel szemben a Duna jobb partján fekvő Esztergom érseksége teljes egészében a Duna bal (felvidéki) partján terült el, vagyis aki az esztergomi egyházmegyéből a székhelyre akart jutni, annak át kellett kelnie a Dunán. Ez arra mutat, hogy a legértékesebb dunántúli területeket az esztergomi érsekség alapítását megelőzően elfoglalta Veszprém. Semmi közelebbit nem tudunk ugyanakkor a győri püspökség felállításáról. Ha a koronakérés idején már legalább két egyházmegye állt István országában, úgy a veszprémi mellett a győri volt a második, ezt Szűz Mária tiszteletére szentelték. A győri egyházmegye a Dunántúl északnyugati részére terjedt ki.
Az esztergomi érsekség az 1001. áprilisi ravennai zsinaton született meg, ahol II. Szilveszter pápa és III. Ottó császár elfogadta István – Aserik-Anasztáz által tolmácsolt – kérését, hogy Magyarországon önálló egyháztartomány jöjjön létre saját érsekséggel, amely immár független a német birodalmi egyháztól. Azért Esztergom lett a magyar egyház központja, mert ez a város számított a királyság székvárosának. Jellemző, hogy István nem a Géza alatt Esztergomban felépített Szent István első vértanútemplomot tette meg érseki székesegyházzá (amelynek bajor, közelebbről passaui kapcsolata nyilvánvalónak látszik), hanem e célra új templomot épített. Ennek elsődleges templomcíme Szent Adalbert volt, némileg később csatlakozott hozzá második védőszentként Szűz Mária. Az első esztergomi érsek az a Domokos lett, aki valószínűleg Gizella kíséretében jött Magyarországra. Őt 1002 után az érseki székben Szent Adalbert tanítványai követték: rövid ideig Radla, szerzetesi nevén Sebestyén, majd 1007-től mintegy negyedszázadig az Istvánnak koronát és pápai áldást hozó Aserik-Anasztáz. Amikor Regensburgi Arnold szerzetes 1030 táján a Dunán hajóval Magyarországra jött, vendéglátója Anasztáz érsek volt. A főpap műveltségéről Arnold becses információkat őrzött meg. Esztergom érsekének fennhatósága a Dunától közvetlenül északra fekvő vidékre terjedt ki, a nyugati Felvidék akkor még zömében csak déli sávjában lakott részére. A magyar királyok koronázásának jogát a mindenkori esztergomi érsek élvezte. E három egyházmegye (a veszprémi, a győri és az esztergomi) lefedte az akkoriban az árpádok tényleges uralma alatt álló terület egészét. Éppen ez a körülmény mutatja a legjobban, hogy az árpádoknak mekkora szerepük volt a latin rítusú egyház intézményrendszerének kiépítésében, hiszen saját uralmi körzetükben állították fel először a püspökségi szervezetet.
A törzsfők leverésével, a világi igazgatási szervezet (a vármegyék) megszervezésével párhuzamosan folyt az egyházmegyék felállítása. Ezt szinte minden olyan püspökség példája igazolja, amely nem az árpádok törzsi államában létesült. Mindjárt igaz ez a megállapítás az erdélyi püspökségre. Miután István 1003-ban legyőzte az erdélyi Gyulát, annak országában – feltevés szerint a Felső-Tisza vidékétől Kolozsig terjedő térségben – hamarosan latin rítusú püspökséget állított fel. Kezdetben az erdélyi egyházmegye egybeesett a nagy kiterjedésű Doboka vármegyével. Attól kezdve azonban, hogy István elfoglalta a dél-erdélyi Keán országát, az erdélyi püspökség dél felé terjeszkedett, Fehér vármegye területére, ugyanis a király Dél-Erdélyben nem alakított ki önálló egyházmegyét. Sajátos helyzetet jelentett az, hogy Erdélyben, István anyai nagybátyjának a területén a 950-es évek óta létezett egy görög rítusú térítő püspökség. Nem tudjuk, hogy ez a 11. század első éveiben ténylegesen működött-e még, mindenesetre a magyarországi ortodox hitű püspökségre vonatkozó bizánci jogigény ekkor is kimutatható. Több ólompecséten szerepelnek ugyanis név szerint megnevezve Turkia (azaz Magyarország) püspökei, csupa görög nevű személy. István – nyugati orientációjának megfelelően – nem fogadhatta el a keleti egyházhoz (tehát végső fokon a bizánci császár fősége alá) tartozó erdélyi térítő püspökséget, hanem azt – ha még egyáltalán megvolt – figyelmen kívül hagyva latin püspökséget alapított. Egy vonatkozásban azonban tekintettel volt az erdélyi térség különleges helyzetére: egyetlen magyarországi kivételként ugyanis itt nem a székhelyről nevezte el az új egyházmegyét. Abban a később megszilárdult gyakorlatban tehát, hogy a legkeletibb magyar püspökséget a terület neve alapján erdélyinek nevezik, az egykori, helyhez nem kötött ortodox püspökség emléke maradt fenn. Erdély latin püspökségének Szent Mihály patrocíniuma talán szintén az ortodox térítő püspökség korára mehet vissza, mivel az arkangyal tisztelete Bizáncban igen erős volt. A 11. század első éveiben (közvetlenül 1003 után) tehát Magyarországon már négy egyházmegye létezett, s ezzel eleget tett annak a kánoni előírásnak, amely szerint egy önálló egyháztartomány létesítéséhez éppen ennyire volt szükség. Az erdélyi püspökség felállításával lezárult a magyar püspökségi szervezet kiépítésének első, csupán néhány évet magában foglaló, rendkívül mozgalmas korszaka. Ebben a folyamatban István családjának, az árpádoknak, valamint anyja rokonságának, a Gyuláknak a területe kapott egyházmegyei szervezetet.
A második szakasz beköszöntére alig néhány évet kellett várni. Ebben már „idegen” törzsfők országai jutottak püspökséghez. A sort a fekete magyarok leverését követően a pécsi püspökség megalapítása nyitotta meg. Az összefüggés a törzsi állam felszámolása, illetve a vármegye- és egyházszervezés között itt szintén nyilvánvaló. István ugyanis 1008-ban győzte le a Dráva-torkolat környéki fekete magyarokat, és már 1009-ben felállította a pécsi egyházmegyét. Ez az egyetlen püspökség, amelynek alapítólevele ránk maradt – ha későbbi átiratban is. Rendelkező része így szól: „Tudja meg minden mostani és jövőbeli hívünk, hogy mi az igen szent apostoli [pápa] egyetértésével, és az ő követe, Azo püspök, továbbá valamennyi hívünk: érsekek, határispánok, ispánok, valamint kisebb [méltóságú] személyek jelenlétében elrendeltük a pécsi püspökség megalapítását Isten és minden szentje dicsőségére, Bonipertet tettük meg oda püspöknek, kiváltságokkal láttuk el azt, és határait megerősítettük.” Pécs Szent Péter templomcíme azzal lehet kapcsolatban, hogy a püspökség megalapításánál Szent Péter (azaz a római pápa) követsége is jelen volt Azo legátus révén.
A pécsi egyházmegye felállítása (éppen azért, mert alapító oklevelét ismerjük) különös élességgel világít rá a király szerepére, ami hasonló lehetett a többi egyházmegye esetében is. Eszerint az uralkodó rendelte el a püspökség megalapítását, vagyis saját elhatározásából keltette életre. Úgy járt el tehát, mintha ez magánügye lenne, s az így létrejött püspökségi szervezet pedig magánegyházi jellegű intézmény. Ebben István megint bajor példát követett, ami jelentősen különbözött az általános német (Ottó kori) helyzettől. Bajor földön ugyanis erős volt a hercegi hatalom a püspökségek felett, a bajor hercegek nem juttattak saját püspökeiknek államkormányzati feladatokat. Püspöki grófságok ott szinte nem is léteztek. Az István által Magyarországon meghonosított egyházszervezeti modell ehhez a bajor példához igazodott: a magyar uralkodó magánegyházaiként tekintett püspökségeire, és nem vonta be a főpapokat a közigazgatásba. A bajor hatáson kívül a magyar egyház még sokféle más impulzust is befogadott. Erre megint csak Pécs nyújt példát, hiszen első püspöke, Bonipert francia származású lehetett. A pécsi püspökség alapítólevele körülírta annak határait, de vármegyéket még nem sorolt fel. Ennek oka alkalmasint abban kereshető, hogy Pécs esetében a püspökség felállítása nem követte, hanem megelőzte a vármegyékét. Mindenesetre a rövidesen itt életre kelő két vármegye (Baranya és Tolna) szorosan igazodott a pécsi egyházmegye határaihoz.
Kevés biztosat lehet mondani a kalocsai egyházmegye legkorábbi történetéről. Hartvik elbeszélése ugyan ad egy változatot erre, de ez hiteltelen koholmány. Eszerint Aszkrik (Aserik) Pécsvárad első, kolostoralapító apátja volt, majd István király még a koronakérés előtt kalocsai püspökké tette, utóbb a megvakult Sebestyén esztergomi érsek helyettesítésére küldte. Három év múltán Sebestyén visszanyerte látását, „Aszkrik pedig érseki palásttal tért vissza Kalocsára”. Aszkrik a valóságban soha nem volt sem pécsváradi apát, sem kalocsai püspök (és érsek), kiváltképpen nem István megkoronázása előtt. Hartvik úgy próbált magyarázatot találni Kalocsa érseki voltára, hogy az ne veszélyeztesse Esztergom elsőbbségét és előjogait. Mivel 1050-ben Kalocsa már érsekségként szerepel, feltehető, hogy eredetileg is annak alapította István. Szent Pál templomcíme kapcsolatba hozható Pécs Szent Péter patrocíniumával, és arra is lehetőséget ad, hogy Kalocsa érsekségét szintén 1009-ből (vagy akörüli időből) eredeztessük. Azt viszont nem tudjuk pontosan megmondani, hogy egy országban miért jött létre két érsekség. Lehet, hogy a kalocsai érsekség területén – a Duna-Tisza közének déli részén és a Szerémségben – szintén fekete magyarok éltek, így a szorosan vett magyar nép számára szerveztek érseki központot Esztergomban, míg egy másik nép, a kavarok számára Kalocsán. Más magyarázat szerint Kalocsa főpapja címzetes érseki titulussal rendelkezett, saját provinciája nem volt.
Ugyancsak az egyházszervezés ezen körébe sorolható és 1009 tájára tehető a Szent János evangélista tiszteletére szentelt egri püspökség felállítása. Egy 13. századi okleveles adat szól István kori alapításáról. Aba Sámuel szállásterületén létesült, így összefüggésbe hozható Aba Sámuel keresztény hitre térésével és István húgával kötött házasságával. István korában a legnagyobb területű egyházmegye volt, hiszen átfogta a Dunántúl és Erdély közti terület északi részét, délen pedig egészen Ajtony államáig húzódott. Az egri püspökség megszervezéséhez kapcsolható a Taksony alatt Magyarországra került besenyő vezér, a Tisza középső folyása mentén szállást foglaló Tonuzoba halála. Anonymus elmondta, hogy „midőn Szent István király az Élet igéit hirdette, / és a magyarokat keresztelte, / akkor Tonuzoba hitben gyenge lévén, / nem akara lenni kereszténnyé, / hanem nejével együtt élve / temettetett az Abádi révbe, / nehogy keresztelve maga és neje Krisztussal éljen örökké, / de fia, Örkénd keresztényként él Krisztussal mindörökké”. 1009-re tehát immár hét latin püspökség létezett a Kárpát-medencében.
Két évtizedes szünet után a nyolcadik egyházmegye 1030-ban kelt életre Marosvár (Csanád) központtal. Ennek első püspöke a velencei származású Gellért lett, a későbbi vértanú, aki talán a burgundiai Cluny monostorában is megfordult tanulmányai során. E püspökség létesítése gyorsan követte Ajtony leverését, hiszen a nagyobbik Gellért-legenda egyértelműen elmondja: amikor István „látta országában a harcok elcsöndesedését, visszahívta a remeteségből Istennek szolgáját, Gellértet”, s az általa alapítani szándékolt püspökség főpapi tisztét Gellértnek ajánlotta fel. Így került Gellért a Maros vidékére, talán maga a főpap szavai szerint „Pannóniának a besenyők határaival érintkező végvidékeire, pogányok közé, akiknek… soha Isten dicsőséges igéjét nem hirdették”. A püspök nagyobbik legendájából kapunk képet arról, hogy mit kellett tennie székhelyén: „Özönlöttek hozzá a nemesek és a nemtelenek, a gazdagok és a szegények, azt kívánva tőle, hogy az isteni Szentháromság nevében keresztelje meg őket. Ezeket úgy fogadta, mintha a saját fiai lennének, s hogy felengedjenek előtte, asztalához is meghívta őket. A király állította ispánok is sokakat odahoztak, akik aztán Keresztelő Szent János monostorában megkeresztelkedtek. A rengeteg nép ott ácsorgott még a temetőkert kapujában is, magukkal hozva ennivalójukat, s azoknak, akik keresztelték őket, nem volt nyugodalmuk, csak éjszaka. Roppant erőpróbának voltak kitéve, de Krisztus nevéért, akinek dolgában helytállni törekedtek, zokszó nélkül s szíves örömest elviselték ezt a fáradtságot. Azoknak pedig, akik már megkeresztelkedtek, a püspök Isten igéjét hirdette lankadatlanul.” A Csanádi püspökséget Szent György vértanú tiszteletére szentelték fel, amiben nyilván szerepe volt annak, hogy Gellért Magyarországra kerülése előtt a velencei Szent György monostor apátja volt. (Ráadásul István serege a nagyobbik Gellért-legenda szerint Szent György segítségével aratott győzelmet Ajtony ellen.)
István halálakor valószínűleg nyolc püspökség létezett az országban, a váci és a bihari alapításával azonban rövidesen tízre emelkedett számuk. A püspöki székhelyeken dómkolostorok létesültek, amelyekben világi papok és bencés szerzetesek éltek együtt. Ez az intézmény azonban hamarosan átadta a helyét a kanonokokat tömörítő (tehát a szerzeteseket már nem magukban foglaló) székeskáptalanoknak.
István egyik legjelentősebb egyházi alapítása a Boldogságos Szűz Mária tiszteletére szentelt társaskáptalan (prépostság) felállítása volt Székesfehérvárott uralkodása második felében, pontosan nem ismert időpontban, talán 1015 után. Mintájául az aacheni palotakápolna szolgált. A fehérvári vár 1009-ben már szerepel a forrásokban, a királyi bazilika szomszédságában palota épült, a király Esztergom mellett Fehérvárt második székhelyének tekintette. Ennek az volt az oka, hogy a kereskedelmi és zarándokutak áthelyezésével Esztergom veszített jelentőségéből, Fehérvár pedig – kedvező földrajzi fekvése révén – felértékelődött. Itt jelölte ki István temetkezőhelyét, vagyis Fehérvár szakrális központ jelleget vett fel. A székesfehérvári társaskáptalanban őrizték a legfontosabb okleveleket, privilégiumokat, az ország történetére vonatkozó krónikákat, kincseket. A fehérvári prépost a 13. század közepétől igen gyakran viselte az alkancellári tisztséget. A 11. század végén készült István-legendák egyetemlegesen hangoztatják a fehérvári egyház gazdagságát és szépségét. A nagyobbik szerint István „magában a királyi székvárosban, melyet Fehérvárnak mondanak, a mindenkor Szűz dicsőséges nevére nevezetes és hatalmas, csodálatos művű bazilika építtetésébe fogott, a szentély falát domborművekkel díszítette, padozatát pedig márványlapokkal rakta ki. Aki látta, tanúskodhat szavaink igazsága mellett; se szeri, se száma a palástoknak, kellékeknek és egyéb ékességeknek, az oltárok körül színaranyból készült táblák sokasága, rajtuk a legdrágább kövek sora, Krisztus asztala fölött csodásan művészi oltármennyezet emelkedik, kincstára pedig színültig tele mindenfajta kristály-, onyx-, arany- meg ezüstedényekkel.” A kisebbik legenda azt emelte ki, hogy István a fehérvári templomban „különböző színű gyöngyökkel ékes, színaranyból készült ereklyetartókat helyezett el a szentély használatára”. Hamuik szerint a király „e felettébb szépséges templomot saját kápolnájának tekintette”, és sokféle kiváltsággal látta el. Az a körülmény, hogy Szűz Mária nemcsak e királyi prépostság, hanem még két további egyházmegye (Győr és Esztergom) védőszentjeként szerepel, mutatja Istvánnak a Szűzanya iránti feltétlen tiszteletét, ami Magyarországnak Szűz Mária számára történt felajánlásában is megnyilvánult.
István a latin szerzetesek (ebben az időben még csak bencések) számára kolostorokat emelt. Ezek ugyanúgy magánegyházi jellegűek voltak, mint a püspökségek. A legkorábbiról, a még Géza fejedelem utolsó évére visszamenő pannonhalmiról már szóltunk. 1002-ben, mikor az egyik Szent Adalbert-tanítvány, a Meseritzből Magyarországra került Aserik-Anasztáz volt az apátja, István kiváltságokat biztosított a kolostor számára. Uralkodása elején István tétova kezdeményezést tett arra is, hogy a pannonhalmi apátság egyházkormányzati jogkört élvezzen. Mivel 1009-ben nincs szó arról, hogy a veszprémi püspökségnek bármiféle fennhatósága lenne Somogy felett, arra lehet gondolni: ekkor még – a viszonyok kiforratlanságának jeleként – Pannonhalma járt el püspöki jogkörrel Somogyban. Utóbb azonban István már nem adott felhatalmazást a királyi monostoroknak az egyre inkább csak a világi papságot megillető egyházigazgatási ügyekben, s így Pannonhalma Somogyot illető jogköre a tizedszedésre korlátozódott, de még ennek jogosságát is vitatták a későbbi veszprémi püspökök. István elképzelésében tehát a monostoroknak szánt szerep hosszú uralkodása alatt megváltozott. Ebben része volt annak, hogy sógora, II. Henrik német király szerzetesi reformot valósított meg, és ennek során nem adott igazgatási megbízásokat a szerzetesi közösségeknek. E mintának megfelelően uralkodása második felében, amikor újabb kolostorok alakultak, István már nem is kísérletezett azzal, hogy kormányzati hatáskörrel ruházza fel azokat. Felfogása szerint ugyanis a szerzeteseknek az volt a feladatuk, hogy imáikkal, könyörgéseikkel álljanak az uralkodó mellett, vagyis szakrális téren segítsék a királyt, továbbá hogy tanítsák a leendő papságot. E feladatuk teljesítését jól jelzi, hogy Pannonhalma neveltje volt az első hazai származású főpap, a még István életében a pécsi püspökségre emelkedett Mór.
Nehéz biztosat mondani arról, hogy mikor jöttek létre az István kori koIostorok. Amelyiknek tudjuk – vagy tudni véljük – a dátumát, az nem korábbi az 1010-es éveknél. A pécsváradi apátság alapítólevelének kelte 1015 (de csak 1037-ben szentelték fel), a zalavári monostor felszenteléséé pedig 1019. Ugyanekkor már létezett a bakonybéli is: a Magyarországon többször megfordult Günther (talán Gizella királyné rokona) az 1010-es, Gellért (a későbbi Csanádi püspök) pedig az 1020-as években remetéskedett itt. Günther komoly szerepet játszhatott Bél alapításában, mivel annak Szent Móric templomcíme egyezik az altaichi monostor patrocíniumával, márpedig Günther ennek volt a szerzetese. A nagyobbik István-legenda le is írta: István a béli kolostort Günther intésére alapította meg. Nem ismerjük a keletkezési idejét a zobori és a somlóvásárhelyi kolostornak. (Ez utóbbi apácáknak adott otthont.) Az István által alapított hat monostor közül öt a Dunántúlon feküdt, egy a Felvidéken, és a hatból ugyancsak öt létesült az árpádok eredeti törzsi államának területén. Nincs bizonyíték arra, hogy István keleti rítusú (ortodox) kolostort alapított volna, de a már meglevőket (Veszprémvölgyben, valamint Ajtony hajdani országában, amely a Marosvárról történt átköltözést követően Oroszlámoson működött) megtűrte.
A nagyobbik István-legenda elmondása szerint „a király az új keletű püspökségeket, illetve apátságokat királyi módra felruházta birtokokkal és udvarházakkal, szolgákkal és jövedelmekkel, valamint szükségleteik szerint bőségesen feldíszítette keresztekkel, edényekkel és egyéb, az istentiszteletnél használatos kellékekkel”. Az uralkodó gondoskodását azonban nem csupán a püspökségek és az apátságok érezték, hanem az kiterjedt még a legkisebb közösségeket átfogó templomokra is. Azon híres rendelkezése, hogy minden tíz falu építsen egy templomot, előírta: a templom számára ruhákról és oltárterítőkről a királynak kellett gondoskodnia. Személyes törődése olvasható ki a 14. századi krónikakompozícióból, amely szerint „István királynak bevett szokása volt, hogy az általa alapított valamennyi egyházat évente legkevesebb három alkalommal felkereste. És midőn ezen egyházakhoz érkezett, először az összes oltárt bejárta, és könyörgéseit egyesével előadta. Végül kimenvén az egész egyházat körbejárta, a falak és a tetők repedéseit vagy hasadékait fürkésző szemmel és akadékoskodóan szemügyre vette, és legott gondoskodott a javításról, s addig nem távozott a városból vagy a faluból, amíg meg nem győződött a helyreállításról.” Ez arra mutat, hogy a 11. század első évtizedeiben még csak igen kevés egyházi intézmény (püspökség, társaskáptalan, kolostor, falusi plébánia) létezett Magyarországon, és azok nagy része is kis területen (elsősorban a Dunántúlon) összpontosult. Istvánnak mindenesetre meghatározó szerepe volt a magyarországi egyházszervezet kialakításában – a falusi templomoktól kezdve az érsekségekig.