I. (Szent) István király (1000-1038), megkoronázása után, hamarosan püspökségeket létesített, amely az általa végzett egyházszervezés révén történt a 11. század elején. Szent István az első püspökségek között szervezte meg a kalocsai egyházmegyét, azonban alapításának ideje bizonytalan. A szakirodalmak többsége egyetért azzal, hogy a kalocsai érsekség egyidős a pécsi püspökséggel, ami azt jelenti, hogy 1009-ben vagy kevéssel ezt megelőzően létesíthették, tehát az 1009-es évszám az elfogadható. Az azonban elég valószínűtlennek tűnik, hogy Kalocsa 998-1002 között, vagy éppen 1002 őszét közvetlenül követően állt volna fel, s ezáltal – Esztergomot nem számolva – Magyarország első három püspökségének egyike lett volna. Kalocsa első püspöke egy bencés apát személyében Aserik-Anasztáz (Asztrik: KMTL) lett, aki egyben a király egyik legfontosabb támasza volt. Aserik-Anasztáz érsekségéről, a következő történet maradt fenn a Hartvik-féle Szent István legenda szerint. A király nemsokára az esztergomi érsekségbe helyezte át Aserik-Anasztázt, mert annak érsekét, Sebestyént, három évig vakság sújtotta. Azonban, mikor Sebestyén visszanyerte látását, Aserik-Anasztáz csak abban az esetben volt hajlandó visszatérni a korábbi székhelyére, ha az érseki címet Kalocsa számára megtarthatja. Ily módon lett Magyarországon már a kereszténységre térésének legelején-más országoktól eltérően-két érsekség.
Területi elhelyezkedése
Asztrik kalocsai érseksége Györffy György szerint talán 1002–1003-tól legfeljebb 1006–1007-ig elképzelhető. Alapítólevél a kalocsai püspökségről, majd érsekségről nem maradt ránk. Az egyházmegye, avagy a székesegyház védőszentjévé Szent Pál térítőapostolt tették. Valószínű, hogy a püspökség eredeti területe magába foglalta, illetve kiterjedt a Duna másik oldalára is, valamint a későbbi pécsi egyházmegye területére, ahol jórészt mohamedán hitű, valamint kisebb részben pogány kálizkavar, úgynevezett fekete magyarok élhettek, akik elismerték István király fennhatóságát, azonban a keresztény térítés békés módszereivel nem voltak meggyőzhetőek. Tehát a főegyházmegye területe elsősorban Pest és Solt megye déli részére, valamint Bács és Bodrog megyékre terjedt ki, ezért eleinte a dél-magyarországi térítés, majd később a török elleni védekezés egyik központjaként töltött be fontos szerepet. A pécsi püspökség alapítóleveléből (1009-ben keletkezett) arra következtethetünk, hogy a két egyházmegye között kezdettől fogva a Duna volt a határ. A középkori Fejér megye a Duna mindkét oldalán terült el, s Kalocsa is hozzátartozott. Dunántúli részét tekintve a Csepel szigettel együtt a veszprémi püspökség része volt; Solt környéke a váci püspökséghez került, délkeleti része pedig Kalocsával mindig is a kalocsai érsekség területe maradt. Bodrogvár, Bácsvár és még Csongrád megyéi is a kalocsai érsekség alá tartoztak. Györffy György felvetése szerint az is elképzelhető, hogy a későbbi csanádi püspökség területe, azaz Ajtony territóriuma avagy törzsi országa, a körülbelül a Maros és az Al-Duna közötti terület is, ehhez az egyházmegyéhez tartozhatott. Udvardy József azon a véleményen volt, hogy a kalocsai érsekség középkori határa a Duna-Tisza közében kiindulva érte el a Tiszát Szeged fölött, illetve a Szerémségben pedig a Mandelosi patak és az Almás patak választotta el a pécsi egyházmegyétől. Az egyházmegye birtokai Fejér, Bodrog, Bács, Szerém, Valkó, Krassó, Hont valamint Gömör megyékben feküdtek. A középkori érsekség központja eleinte Kalocsa volt, majd az érsekek az 1090-es évektől egy évszázadon át Bács várában tartózkodtak. Ettől kezdve két központja lett az egyházmegyének. Így alakult ki az 1968-ig megőrzött kettős név: kalocsa-bácsi érsekség. Szent László király korától (1077–1095) már több oklevélben is szerepel a bácsi érsek. III. Béla király, országának jövedelem kimutatásában azt írta, hogy a kalocsai érsek székhelye Bácson van. 1266-ban találkozhatunk először a „kalocsai és bácsi érsek” elnevezéssel, majd jóval később az „egyesített kalocsai-bácsi” érsekségről írnak.
A bácsi székeskáptalan jogait III. Ince pápa erősítette meg 1201-ben, azonban csak 1211-ből vannak róla emlékeink. A kalocsai székeskáptalanról 1198-ban történik említés, de csak 1214-től maradtak fenn emlékek róla. Tehát Kalocsán és Bácson is volt székeskáptalan. A kalocsai káptalan Szent Pálról lett elnevezve, s a tőle nagyobb bácsi székeskáptalan is. A társaskáptalanok közül a kalocsai érsekség területén a titeli Isteni (Szent) Bölcsességről nevezettet I. (Szent) László és öccse, Lambert herceg alapította meg, míg a háji Szent Lőrincről nevezettet III. Béla királynak az 1186-ban nőül vett felesége, Capet Margit királyné, amely nagyobb káptalan lehetett, s közvetlenül az esztergomi érsek alá tartozott. A kői (Bánmonostor) Szent István diakónus első vértanúról elnevezett székeskáptalan 1229-ben, míg a Szent Irenaeusról nevezett szenternyei pedig 1247-ben alakult meg.
Egyházi igazgatás
A kalocsai érsekségben öt főesperesség volt: maga a székesegyházi, azaz a kalocsai, amit néha sárközinek is írtak (először 1233-ban); a bodrogi (1219); a bácsi (1229); a szegedi (1199) valamint a szerémi (1216). Közülük a bodrogi, a bácsi és a szerémi területe azonos volt az akkori vármegyékkel. A kalocsai káptalanhoz kettő, azaz a bodrogi, s maga a székesegyházi; valamint a bácsi káptalanhoz pedig három, azaz a bácsi, a szegedi és a szerémi főesperesség tartozott. Szegedet és környékét ölelte fel a szegedi főesperesség, míg a sárközi vagy kalocsai a Duna mentén húzódott. A kalocsai érseki tartomány része volt a középkorban a csanádi, a váradi, az erdélyi, a zágrábi (a 15. század végén Esztergom alá kerül), a szerémi, a boszniai, valamint a rövid ideig fennálló nándorfehérvári, bodonyi, szörényi és argyasi püspökség is.
A pápai tizedjegyzékben sajnos csak a bácsi és szerémségi plébániák nevei vannak feltüntetve, összesen 120, azonban ezt más forrásokkal kiegészítve közel 300 plébániát lehet összeszámolni az egyházmegye területén a török előtti időkből. Egyedülállónak mondható Magyarországon a kőinek (később szenternyeinek, majd végül szeréminek) nevezett püspökség, melyet 1229-ben alapított Csák Ugrin kalocsai érsek. Ugyanis ez nem külön egyházmegye volt, hanem a kalocsai érsekség területén lévő úgynevezett magánpüspökség, melynek az volt a feladata, hogy helyettesítse az érseket a főpapi tevékenységében.
Szerzetesrendek
A kalocsai érsekség területén működő szerzetesrendek: a bencések (Bodrogmonostor, Dombó, Nagyolasz … stb.), a ciszterciek (Pétervárad), a premontreiek, az ágostonrendi kanonokok és remeték (Derzs és Bács közelében), a pálosok, a Szent Sír-kanonokrend, a ferencesek (Szeged, Bács, Küllőd … stb.), a domonkosok (Szeged, Bodrog és Czoborszentmihály, azaz a későbbi Zombor), a johannita keresztes lovagok és apácák.
A kalocsai érsekek egyik feladata az volt a 13–15. században, hogy gátat szabjanak a boszniai bogumilizmus eretnekség terjedésének, illetve a 15. században a Szerémségben fellépő huszitizmusnak. János érsek (1202–1205) érte el azt, hogy a vezetők tegyenek esküt a tévtanaiknak az elhagyására, azonban ez az ígéret nem szólt hosszú időre, így hát Csák Ugrin érsek (1219-1241) fegyveresen is kénytelen volt fellépni ellenük. Ezt a küzdelmet folytatta még Benedek (1241-1254) és István (1266-1278) érsek is. Arra is törekedtek az érsekek, hogy egyesítsék a szomszédos országok egyházait is a rómaival.
1241. április 17-én Csák Ugrin, az egyházmegye 21. érseke a szerencsétlen sajómenti ütközetben esett el. A tatár megszállás idejéről az egyházmegye népének megpróbáltatásairól írásos emlék nem maradt ránk; azonban azt tudjuk, hogy a tatárok elvonulása után beköltöző, de még vándorló, nomád pásztorkodást űző, pogány kunok garázdálkodásaitól sokat szenvedett az egyházmegye. A kunok térítésében csak Szigeti István érsek (1367-1382) ért el eredményeket.
1390-ben törtek be először Szerém megyébe a törökök, s ezután kezdődött el az egyházmegye déli részén Szerém, Bács és Bodrog megyék területén a menedéket kereső délszláv népesség beköltözése.
Kapisztrán Szent János Küllődről indulva a Dunán hajózott Nándorfehérvár alá keresztes seregével, ahol Hunyadi Jánost támogatva 1456. július 26-án fényes győzelmet arattak, s ezáltal 70 évre elhárították a török veszedelmet az országtól és az egyházmegyétől is.
Tomori Pál érsek (1523–1526), akinek katonái a Délvidéket védték, 1526. augusztus 29-én fővezérként, a mohácsi csatamezőn vesztette életét a királlyal és hat püspökkel. 1529-ben Kalocsa is az oszmán hódítók kezére került. A mohácsi vészt követően pedig, a törökök kifosztották Budát, majd a Duna-Tisza közén hazafelé vonulva feldúlták Bácsot is. Buda 1541-ben történt elfoglalása után az egész egyházmegye török uralom alá került. Ettől kezdve a kalocsai érseki címet egy-egy, a királyi Magyarország területén fekvő egyházmegye püspöke viselte.