Rep el seu nom de l'antiga Pallantia, una de les ciutats més importants de la part habitada pels vacceus. Després d'algunes victòries en la seva defensa, contra els romans, va quedar subjecta per fi al seu domini al llarg de cinc segles. Saquejada i destruïda cap al 456 pel rei visigotTeodoric, i reedificada, va brillar durant la monarquia visigoda amb els seus bisbes Murila, Conanci, Ascari, Concordi i Baroald, que van subscriure les actes d'onze dels concilis de Toledo entre els anys 589 i 693.
Destruïda de nou en la invasió dels àrabs, així va continuar durant més de tres segles de silenci, amb bisbes en l'exili, fins que va ser restaurada el 1035 per Sanç III de Pamplona i Beremund III de Lleó. Tornant, a partir d'aquest mateix any, una sèrie ininterrompuda de 96 bisbes.
Els límits geogràfics establerts per Sanç III el Major de Navarra per a la diòcesi de Palència el 1034, estaven assenyalats pel riu Cea fins al Duero, i el Pisuerga fins a Peñafiel i Portillo. Però el 1035 Beremund III va avançar molt la diòcesi de Lleó cap al llevant, mentre que la de Palència s'estenia més enllà del Pisuerga. No obstant això el 1059 Ferran I va fer alguns reajustaments fixant els límits a l'orient i l'occident.
El 1595 es va erigir la diòcesi de Valladolid i es desmembraren de la de Palència els arxiprestats de Portillo, Simancas i Tordesillas. L'últim gran canvi de límits va tenir lloc el 1955, en fer coincidir els límits eclesiàstics amb els de la província civil.