En verano de 1929, los dirigentes morados inscribieron al club en el Campeonato Regional de Segunda categoría de la Federación Castellano-Leonesa, en el que le correspondería enfrentarse a la Unión Sportiva de Valladolid y la Unión Deportiva Astúrica de Astorga, para disputar el campeonato, que daba derecho a la disputa de la promoción para el ascenso a Primera categoría. Sin embargo, el 7 de Octubre, pocos días antes de publicarse el calendario, el Palencia se proclama campeón, por haberse retirado sus dos rivales. El conjunto morado dedicó la temporada a jugar amistosos, en espera de la promoción, pero esta no llegó a disputarse, ya que el cuarto y último clasificado de Primera categoría, la Unión Deportiva Española de Salamanca, se había retirado de la competición. El Palencia consiguió el primer ascenso de su historia, sin haber disputado ni un partido oficial.

La temporada 1930-1931 los morados participaron en el campeonato de Primera categoría, teniendo como rivales al Real Valladolid Deportivo y la Cultural Leonesa, tras la retirada de la Ferroviaria de Valladolid. Esta vez sí se disputó el campeonato, con dos plazas para la Copa de España en juego. Se jugó a cuatro vueltas y, en los ocho partidos, los morados sólo empataron uno y perdieron los otros siete, debiendo participar en la promoción de permanencia, que finalmente tampoco se llega a disputar, manteniéndose el Palencia en Primera categoría.

El 16 de Agosto de 1931 se celebró una importante Asamblea en Gijón, participando clubs de las Federaciones de Asturias, de Cantabria y de Castilla-León. El objetivo era formar un campeonato mancomunado de las tres regiones, que aportase mayor competitividad. En principio, participarían en ese campeonato Sporting de Gijón, Oviedo, Club Gijón, Racing de Santander, Eclipse, Valladolid y Cultural Leonesa. El representante del Palencia solicitó ser incluido en lugar de la Cultural, recién desaparecida, aceptándose su petición. Pero, después del acuerdo, el representante del Valladolid comunicó que su club había decidido participar en otro campeonato mancomunado, con los clubs de las Federaciones de Centro y Aragón. Los equipos asturianos y cántabros entendieron que la competición quedaba devaluada sin el club pucelano y el acuerdo se rompió.

Una semana más tarde, se celebró en Valladolid la Asamblea regional de la Federación Castellano-Leonesa, nuevamente con representación morada, a cargo de los señores Serrano y Velasco. La Federación reconoció el derecho del Palencia a jugar en Primera categoría, pero con la desaparición de la Cultural y la “fuga” del Valladolid para participar en el campeonato mancomunado de Centro y Aragón, los morados se quedaron sin rivales. Se decidió que, para llenar las fechas, el Palencia participase en el campeonato de Segunda categoría, sin tener más trascendencia su clasificación, en un grupo integrado por el recién fundado U.D. Leonés y los palentinos Española F.C., Racing Castilla y C.D. San Isidro.
El papel del conjunto morado, no fue bueno, consiguiendo tan solo dos victorias, un empate y tres derrotas, aunque tampoco la clasificación tenía mayor importancia.

El verano de 1932 trajo consigo la noticia de la desaparición de la Federación Castellano-Leonesa de Fútbol, por integrarse el Valladolid en la Federación Centro. El 23 de Julio el Palencia recibió la notificación de que las provincias de Burgos y Palencia se integrarían en la Federación Cántabra. Sin embargo, la Federación Nacional, decidió que las provincias de León y Palencia quedasen integradas en la Federación Asturiana, que celebró su Asamblea el día 1 de Agosto y decidió que la Primera categoría estuviese integrada por Sporting de Gijón, Oviedo, Stadium de Avilés y Club Gijón, y la Segunda, por Racing de Sama, Sportiva Ovetense, C.D. Palencia y U.D. Leonés.
Ante este descenso de categoría, la Directiva morada realizó varias gestiones, que culminaron el 25 de Agosto, con el anuncio de que la provincia de Palencia se integraría en la Federación Cántabra y el C.D. Palencia participaría en el campeonato de Primera categoría junto al Racing de Santander, Eclipse F.C., C.D. Torrelavega y Tetuán F.C., todos ellos cántabros. Los dos primeros clasificados participarían en la Copa de España y los dos últimos jugarían la promoción de permanencia. Para llegar a este acuerdo, los dirigentes morados se comprometieron a abonar a cada uno de sus rivales los gastos de desplazamiento hasta la capital palentina.

El papel del Palencia no fue muy brillante, ocupando finalmente la penúltima plaza, por delante del Tetuán F.C., que le acompañó a la promoción, jugada por sistema de Liga, en la que se incluyó a los dos primeros clasificados de segunda categoría, Santoña F.C. y C.D. Naval de Reinosa. Estos dos últimos ocuparon las dos primeras plazas, ascendiendo a Primera categoría, mientras los morados, terceros, quedaban pendientes de una posible ampliación de dicha categoría a seis equipos.

El desbarajuste federativo llegó a extremos insospechados en 1933. La Federación Cántabra decide crear dos subcomités locales, uno en Burgos y otro en Palencia, cada uno organizando sus competiciones de Segunda y Tercera categoría, cuyos respectivos campeones deberían eliminarse entre sí y contra el campeón de la zona de Cantabria, por una plaza de ascenso. El 13 de Agosto se celebró la Asamblea de la Federación Cántabra, y el Palencia solicitó participar en Primera categoría, pero sin abonar gastos de desplazamiento a sus rivales. La Asamblea “tomó en consideración” la propuesta, sin pronunciarse sobre ella. El día 3 de Septiembre, comenzó el campeonato, y el Palencia no estaba incluido en él, viéndose relegado así a la Segunda categoría. Al ser el único club de la provincia en dicha categoría, se proclamaría campeón y pasaría directamente a jugar la promoción.

Recibió entonces el Palencia una oferta para participar en el campeonato de Segunda categoría del campeonato mancomunado de Castilla – Andalucía, sin dejar de pertenecer a la Federación Cántabra. El 18 de Septiembre, la Directiva comunicó que aceptaba esta propuesta, siendo incluido en el grupo Norte, junto a Salamanca, Zamora y los vallisoletanos Canario, Delicias y Española. En otra discreta temporada, los morados ocuparon una intrascendente cuarta plaza.

El verano de 1934 trajo el retorno a la Federación Cántabra, esta vez con competición incluida, al incluirse a los morados en el campeonato de Segunda categoría, junto a Burgos, Mirandés y los rivales locales del Castilla. El Palencia consiguió de forma brillante su primer título y, con él, el derecho a disputar la promoción de ascenso. Esta se disputó contra el Laredo, en el campo teóricamente neutral de Los Arenales, en Santander, y finalizó con la victoria morada por 3-1 y el ascenso a Primera categoría.

Pero el verano de 1935 trajo la creación de la Federación Leonesa, integrada por los clubs de las provincias de León, Zamora y Palencia, pasando los morados a jugar el campeonato regional de Primera categoría, junto a C.D. Zamora, S.D. Bañezana, S.D. Ponferradina y Cultural Leonesa. Los campeones jugarían las eliminatorias para clasificarse para la Copa de España. En una accidentada temporada, el Palencia finalizó tercero.

Tras la guerra civil, se suprimió la Federación Leonesa y sus clubs quedaron integrados en la Asturiana que, más tarde, se uniría a la Cántabra para formar la Astur-montañesa, y así siguieron hasta 1953, en que palentinos y leoneses quedaron integrados en la Federación Oeste, creada un año antes y que, con el paso de los años, pasó a llamarse Federación de Castilla y León de Fútbol, como la conocemos actualmente.

Atrás quedaron unos primeros años en que el cambio de Federación, las renuncias de equipos y los ascensos y descensos “a capricho” tuvieron el corazón de los aficionados palentinos en vilo, al no saber hasta última hora en qué categoría de qué región les tocaría competir esa temporada.