A história da Arquidiocese da Paraíba remonta ao dia 27 de abril de 1892 quando o Papa Leão XIII, pela Bula “Ad Universas Orbis Ecclesias”, desmembrou o território que compreende os estados do Rio Grande do Norte e da Paraíba, constituindo assim uma nova Diocese com sede na então Capital paraibana. A nova Diocese só foi instalada dois anos depois, aos 4 de março de 1894, com a chegada do seu primeiro Bispo, Dom Adaucto Aurélio de Miranda Henriques. Homem clarividente e empreendedor, Dom Adaucto fundou, logo no dia de sua chegada, o Seminário e o Colégio Diocesano.

Aos poucos, parte do território original da Diocese foi se reconfigurando em outras circunscrições. Em 1909 é criada a Diocese de Natal, desmembrando todo o Rio Grande do Norte. Em 1910, tanto a Diocese de Natal quanto a então Diocese da Paraíba ficaram sendo sufragâneas da recém-elevada Arquidiocese de Olinda e Recife. No dia 6 de fevereiro de 1914, apenas vinte anos depois da chegada de Dom Adaucto, pela Bula “Maius Catholicae Religionis Incrementum”, o Papa São Pio X cria a Diocese de Cajazeiras no sertão paraibano e, ao mesmo tempo, eleva a Diocese da Paraíba à condição e dignidade de Arquidiocese e Sede Metropolitana, tendo por sufragâneas as duas Dioceses que haviam sido desmembradas do seu território: Natal e Cajazeiras.

Em maio de 1949 o Santo Padre, Papa Pio XII, criou a Diocese de Campina Grande e dez anos depois, em janeiro de 1959, já sob João XXIII, foi criada a Diocese de Patos, com território desmembrado das Dioceses de Cajazeiras e Campina Grande. Em 1980 foi criada a caçula das Dioceses paraibanas: Guarabira.

Dom Marcelo Pinto Carvalheira, então Arcebispo, solicitou da Sé Apostólica a concessão do título de Basílica Menor à Catedral Metropolitana de Nossa Senhora das Neves. Em 1997, após grandiosa reforma do templo, o título é concedido pelo Papa João Paulo II.