Ismereteink számos ponton bizonytalanok a kalocsai érsekség kora középkori történetével kapcsolatban. Források hiányában ma sem tud egységesen állást foglalni a történettudomány olyan fontos kérdésekben, mint pl. az alapítás pontos ideje, az érseki rang elnyerésének okai-körülményei, az első főpap, Asztrik személye és életútjának részletei.
Szent István királyunk feltehetően 1002-ben, az első püspökségek között szervezte meg a kalocsai egyházmegyét, melynek élére Asztrik személyében olyan művelt, széles látókörű főpap került, aki korábban Szent Adalbert környezetében élt, majd Szent István szolgálatába állva fontos megbízatást teljesített: koronát és a magyar egyházszervezést jóváhagyó pápai iratot hozott Rómából első királyunk számára. Asztrik részt vett a fekete magyarok térítésében, s a további dél-magyarországi térítés szervezőjeként fontos szerepe lehetett abban a folyamatban, melynek eredményeképpen a kalocsai püspökség minden bizonnyal még Szent István életében érseki rangra emelkedett.
A székhely, Kalocsa választását valószínűleg a korabeli politikai szempontok indokolták: a Duna-Tisza köze a honfoglalás időszakától a magyarság vezértörzsének, az Árpádoknak a szállásterülete volt, melynek Kalocsa az egyik korai központja lehetett. Kedvező körülményt jelentett a Duna közelsége is. Az említett szempontok azonban hamarosan megváltoztak, és Szent László királyunk idején az érseki tartomány területének déli irányú növekedése miatt az egyházmegye központja délebbre, könnyebben elérhető helyre települt. A kalocsai érsekek így az 1090-es évektől egy évszázadon át új székhelyükön, Bács várában tartózkodtak.
A kalocsai érsekség a korabeli szokásoktól eltérően jött létre, hiszen Kelet-Közép-Európában ekkoriban országonként csak egy érseki tartományt szerveztek (az alkalmazott joggyűjtemények 10-12 püspökséghez rendeltek egy érsekséget), Magyarországon pedig Esztergom után Kalocsa már egy második érsekséget jelentett, ráadásul jelentősebb számú hozzárendelt egyházmegye nélkül kezdhette meg működését. Az érseki tartomány területe csak fokozatosan alakult ki, így az érseki státus elismertetése (Rómában és Esztergomban) is hosszú folyamat lett, és egészen a 12. századig elhúzódott. Magyarország déli terjeszkedése során viszont az érsekség olyannyira megerősödött, hogy az 1160-as években már versengés kezdődött az elsőbbségért az esztergomi és a kalocsai érsekek között, s a rivalizálás végigkísérte a 13. századot.
Az érseki székbe kerülő főpapok művelt, gyakran külföldi egyetemeken tanult személyek voltak, akik udvari szolgálatuk és érsekségük során tanítói, diplomáciai, egyházszervezői, hittérítő és tudományos-irodalmi tevékenységet is végeztek, és ha kellett, a hadak élére álltak. Jó példa minderre Csák Ugrin érsek (1219-1241) élete, aki kinevezése előtt a királyi kancelláriát vezette, majd érsekként Boszniában harcolt a bogumil eretnekek ellen, és sikerei elismeréseként báni kinevezést is kapott. 1229-ben megszervezte a Kői (később Szerémi) püspökséget, melyet minden bizonnyal a további térítések kiindulópontjául szánt. Ugrin érsek 1241-ben, a Muhi csatában halt hősi halált.
Az egyházmegyében a tatárdúlást az átvonuló kunok pusztításai súlyosbították. Az újjáépítésben IV. Béla mellett fontos szerepet játszottak a kalocsai érsekek. Megkezdődött a magyar várrendszer kiépítése, melynek során Kalocsán is komoly erődítmény épült a korábbi érseki lak helyén. A 13. század második felében az érsekek erejüket a pogány kunok megtérítésére összpontosították, de a térítési kísérletek sorra kudarcba fulladtak. A 14. században azután a koldulórendek (ferencesek, domonkosok) segédkeztek a katolikus hit terjesztésében.
A székesegyházak mellett működtek az érsek tanácsadó testületei, a káptalanok. Tagjaik, a kanonokok elsősorban teológiai-, jogi-, olykor orvosi műveltséggel is rendelkeztek, és a káptalani iskolákban képezték a kor írástudóit, a klerikusokat. Albert és Déméndi László kalocsai prépostok orvosként is tevékenykedtek Nagy Lajos király udvarában.
A következő évszázadot már a védekezés, a déli határok megerősítése jellemezte a Balkánon lendületesen előretörő török birodalom árnyékában. A helyzetet nehezítette, hogy a 15. század végén a kalocsai érsekség nehéz anyagi helyzetbe került, s a bácsi és szerémi részeken terjedt a huszitizmus. Mindeközben az érsekekre hárult saját katonaságuk mellett az egyházmegyében lévő királyi várak seregeinek eltartása is. A bajt tetézte, hogy 1520-tól három éven át betöltetlen maradt a kalocsai érseki szék, és megfelelő vezetés híján a birtokok jövedelmeit elprédálták. 1521-ben török kézre került a Délvidék legfontosabb erődítménye, Nándorfehérvár. A kalocsai érsekség ezután közvetlen fenyegetettségben élt, déli területeiről a lakosság menekülni kezdett. Ilyen körülmények között került az érseki székbe Tomori Pál ferences szerzetes, aki néhány éves hősies munka, a haza védelmére tett erőfeszítések után 1526-ban a magyar seregek élén, a mohácsi csatamezőn vesztette életét. 1529-ben Kalocsa, az érseki székhely is az ellenség kezére került. Ettől kezdve másfél századon át a török volt itt az úr.
Az első érsek, Asztrik ábrázolása egy 18. századi festményen, és a Mohácsnál hősi halált halt
Tomori Pál érsek szobra a Szentháromság téren