A magyarok első királya, Szent István (997-1038) alapította a kalocsai székhelyű püspökséget, közvetlenül Esztergom (1001) és Veszprém után, valószínűleg már 1002-ben. Területe Solt magasságától a Duna-Tisza közén át déli irányban egészen a Száva folyóig terjedt, és az ókori Szerémséget és Sirmium városát is magában foglalta. Első főpapja Asztrik volt, aki az ezredik év őszén II. Szilveszter pápától koronát hozott István fejedelem részére. Feltehetően neki köszönhető, hogy a Kalocsai Püspökség rövid időn belül érsekség rangjára emelkedett, és ő építtette az első székesegyházat Kalocsán.

Asztrik érsek ábrázolása az érseki palota egyik festményén (18. sz.)

Az érsekség területének nagy része a várostól déli és délkeleti irányban feküdt, érseki tartományát pedig a Csanádi, Nagyváradi, Erdélyi, majd később a Zágrábi Egyházmegyék képezték. Szintén az érsekséghez tartozott hat missziós püspök, amely jelzi a térítő és egyházszervező jelleget. Szent László király (1077-1095) az érsekség számára délen Bács városát illetve várát jelölte ki székhelyül, föltehetőleg azért, hogy a szomszédos bizánci birodalom egyházának hatását ellensúlyozza és a Balkánról beszivárgó eretnekségeknek gátat vessen.  Így az 1090-es évektől kezdve a kalocsai-bácsi érsekségnek két székhelye, és ennek megfelelően két székesegyháza, székeskáptalanja volt. Mind Kalocsa, mind Bács egyházának védőszentje Szent Pál apostol volt, s a két székhely ellenére az egyházmegyének mindig csak egy érseke volt. Az érsek a középkorban gyakrabban tartózkodtak a déli székhelyen, emellett országos tisztségeik is voltak: a királyi kancelláriát is vezették, később pedig a bodrogi és a bácsi vármegye főispáni tisztét is ellátták.

A tatárjárás (1241-1242) a Kalocsai Érsekség területén is súlyos pusztítással járt. A templomok, monostorok és kolostorok újraépítése után a XIV. században kb. 300 plébániát említenek a források. A XV. században a török birodalom terjeszkedése egyre több gondot okozott az érsekeknek, akik ekkor inkább voltak hadvezérek, mint főpapok. Magyarország érdeke tőlük a déli határok katonai védelmét követelte meg. II. Szulejmán szultán seregei 1526-ban Mohácsnál csaptak össze a magyar seregekkel, amelyek hadvezére, Tomori Pál kalocsai érsek (1523-1526) volt. Tomori érsek életét áldozta az országért és az Egyházért.

Tomori Pál érsek szobra Kalocsán, a Szentháromság téren

A vesztes mohácsi csatát a nagyszámú templom, köztük a Bácsi székesegyház pusztulása követte. Nyom nélkül pusztult el a középkorban virágzó monostorok jelentős része. A másfél százados török uralom a magyar lakosság megfogyatkozását, és a délszláv népek betelepedését hozta. Az érsekek nem tartózkodhattak egyházmegyéjük területén, és a lelkipásztorkodást - mivel egyházmegyés pap alig akadt - bosnyák ferences szerzetesek végezték. Buda várának 1686-os felszabadulása után az érsekség területén is megindulhatott az újjáépítés, mindenekelőtt az elnéptelenedett falvak betelepítésével.
A XVIII. században számos falu, főként Bácskában, német telepeseket fogadott, de a horvátok, bunyevácok és sokácok is érkeztek nagy számban. A század derekára megépült a jelenlegi székesegyház, a nagyszeminárium és végül az érseki rezidencia. A barokk század végére a hatalmas kiterjedésű érsekség benépesült és újjáépült, mindössze a régi déli székhely, Bács vára maradt romokban. Az említett munkában jelentős szerepe volt a zajezdai báró Patachich család két tagjának akiknek érseksége mintegy keretezi az újjáépítési folyamatot: Patachich Gábor (1733-1745) és Patachich Ádám (1776-1784).

Patachich Gábor érsek (1733-1745) és Patachich Ádám érsek (1776-1784) portréja (érseki palota)

A XIX. században nagy mértékben fejlődött az egyházi intézményrendszer (iskolák, árvaházak, kórházak), az egyházmegye egyre több pontján jelentek meg - és éreztették jótékony hatásukat a hitélet fellendítése terén - a szerzetesrendek. Bőkezű támogatóik, gyakran alapítóik voltak az érsekek, így pl. az európai hírű, természettudományos érdeklődésű Haynald Lajos bíboros érsek (1867-1891), valamint az egyházművészetek iránt fogékony Császka György érsek 1891-1904).

   
Haynald Lajos érsek (1867-1891) és Császka György érsek (1891-1904)

A XX. században az igazságtalan trianoni békeszerződés az érsekség területének kétharmadát Jugoszláviához csatolta, melynek nyomására a Szentszék 1923-ban külön apostoli kormányzóságot, 1968-ban pedig új püspökséget hozott létre a Kalocsától elszakított bácskai területen. A kommunista egyházüldözés Kalocsán is éreztette hatását. Grősz József érseket (1943-1961) koncepciós perben elítélték és 1951-től 1956-ig volt bebörtönözve. A diktatúra hanyatlásával a lelkipásztorkodás is szabadabbá vált.

Grősz József érsek (1943-1961) portéja (részlet, Kontuly Béla, 1950)

1993-ban II. János Pál pápa újjászervezte a kalocsai főegyházmegyét, kiegészítve a Váci Püspökségtől és a Pécsi Egyházmegyétől átvett területekkel. A Kalocsa-Kecskeméti Érsekség Kecskeméten társszékesegyházat kapott, területe azóta lényegében megegyezik Bács-Kiskun Megye igazgatási területével, az érseki tartomány egyházmegyéi a Szeged-Csanádi és a Pécsi Püspökség.

A Főegyházmegye bemutatása, történetének és irodalmának bővebb kifejtése a Főegyházmegyei Levéltár honlapján, külön lapon olvasható.