Autillo aparece como cabecera de un alfoz en un documento de Fernando I del año 1059. El origen de esta localidad puede deberse al castillo que poseía don Gonzalo Ruiz de Girón, señor de Frechilla y mayordomo de la reina, situado sobre una pequeña altura. A él se retiró en 1215 la reina Doña Berenguela, hermana del rey Enrique I, enfrentada con el tutor real, el poderoso conde Alvar Núñez de Lara.
Sitiada la fortaleza por las tropas del conde, doña Berenguela solicita la ayuda de su hijo, el infante don Fernando, que al frente de un ejército de quinientas lanzas y el doble de peones, fuerza el levantamiento del cerco al enterarse el de Lara de su llegada.
El 6 de junio de 1217 fallece el rey Enrique I en el alcázar palentino tras caerle en la cabeza una teja unos días antes. Con el fin de ganar tiempo para sus planes, el conde manda llevar el cadáver a su fortaleza de Tariego. No obstante, enterada doña Berenguela de la noticia, renuncia al trono a favor de su hijo, que se proclama rey de Castilla en Autillo de Campos el 14 de junio de ese mismo año. Trece años más tarde es proclamado también rey de León, dando lugar a la unión definitiva de las coronas de ambos reinos.
Fernando III "El Santo" recompensa en 1221 a don Gonzalo Ruiz de Girón por su fidelidad y los servicios prestados otorgándole el señorío de Autillo de Campos. De la fortificación únicamente queda el nombre de la Calle del Castillo como recuerdo.
A mediados del siglo XIV la iglesia parroquial de "Autiello" se dedicada a Santa María. Aparece en el Becerro de las Behetrías como lugar solariego de Doña Inés, viuda de Ferrant Rodríguez de Villalobos, quien recibe por martiniega 3 maravedís del que tiene 2 bueyes, 15 dineros del que tiene uno, mientras que los que carecen de bueyes pagan un maravedí. También percibe 300 maravedís anualmente en concepto de yantar, mientras que al Rey le corresponden los derechos de servicios y moneda.
Enrique II concede en 1367 la villa a Alvar Rodríguez de Escobar, sobre la que Isabel Rodríguez de Escobar funda mayorazgo en 1452.
Comparada con otras localidades de la Merindad de Campos, durante la primera mitad del siglo XV cuenta con una población media alta comprobando las cantidades que pagan en concepto de pedidos y monedas, que en 1409 ascienden a 3.880 maravedís, aumentando a 10.430 en 1456.
Durante los siglos XV al XVIII ejerce el señorío la familia de los Reinoso, descendiente de los Girón, que venidos a menos, cometen numerosos abusos.
Destaca a mediados del siglo XVI la importante figura de Francisco de Reinoso, Obispo de Córdoba y Abad de Husillos, que llega a ser maestresala durante el pontificado de Pío V. Su hermano Manuel de Reinoso es Arcediano de Campos y Canónigo de Palencia, mientras que dos de sus hermanas Inés y Catalina, se ven implicadas en el Auto de Fe de 1559 celebrado en Valladolid.
En 1528 los 113 vecinos pecheros pagan 20.560 maravedís en concepto de "Servicios de Su Majestad". Años más tarde, en 1591, la población asciende a 167 vecinos, de los que 160 son pecheros, mientras que los 7 restantes pertenecen al clero secular.
Datos de 1631 indican que la localidad, incluida en el partido de la ciudad de Palencia, cuenta con 156 vecinos, 566 personas, con un consumo anual de 20 fanegas de sal. Quince años más tarde, se censan 80 vecinos y se incluya la villa en el partido de Campos.
El vecindario en 1712 está formado por 115,5 vecinos, entre los que se encuentran 17 viudas consideradas como 8,5 vecinos, y 23 pobres. También hay 5 mendicantes y la viuda de un hidalgo que no tienen la consideración de vecinos.
Como villa de señorío de la Sra. Antonia Ventura de Zúñiga y Reinoso, aparece en 1752, con una población de 204 vecinos, en el que se incluyen 2 viudas contadas como un vecino y 18 religiosos. Forman el casco urbano 203 casas habitables, además de 2 inhabitables y 3 solares.
En 1768 la población es de 981 habitantes, de los que 391 son hombres y 480 mujeres. Por esas fechas la localidad tiene varias cofradías, la del Santísimo Sacramento, la de la Cruz, de Ánimas, Nuestra Señora del Rosario, San Sebastián, Nuestra Señora de la Paz y Nuestra Señora del Castillo. Además hay dos hermandades de la Orden Tercera, una de hombres y otra de mujeres.
Figura en el nomenclátor de 1785 como villa de señorío secular, en la provincia de Palencia, partido de Campos, con Alcalde Mayor y Alcalde ordinario de señorío, y dos años más tarde aparece como señorío secular del Marqués de Olías bajo la autoridad de un Alcalde Mayor de Señorío y con una población de 882 personas, de las que 442 son hombres y 440 mujeres.
Por profesiones hay 84 jornaleros, 47 labradores, 33 artesanos, 21 criados, 13 estudiantes, 10 fabricantes, 5 comerciantes, 5 militares, 1 escribano, 1 dependiente de Inquisición y 1 dependiente de Cruzada. Asimismo, relacionados con la iglesia hay 8 beneficiados, 1 teniente de cura, 1 sacristán y 1 acólito.
Sebastián Miñano informa en 1828 que Autillo de Campos tiene 742 habitantes, considerados como 150 vecinos. Cuenta con unas 4.000 cabezas de ganado lanar y produce trigo, cebada, avena, diversas leguminosas, 3.500 cántaras de buen vino y fabrica mucho queso que se vende en Villalón. También dispone de telares de estameñas y bayetas ordinarias.
A mediados del siglo XIX, según informa Pascual Madoz, forman el casco urbano 164 casas además de un palacio medio derruido de los marqueses de Olias, que ahora pertenece a Grimaldo. Los 152 vecinos, unas 790 almas, disponen en la villa de 2 tiendas de abacería y géneros coloniales y cuentan con cerrajero, carpintero, sastre, 2 zapateros, 2 panaderos y 20 hornos donde cocer el pan. Se siguen fabricando estameñas y el queso con el nombre de Villalón se vende en Madrid.
Becerro de Bengoa en 1874 informa de la existencia de 696 habitantes y 176 casas, mientras que a finales de 1877 la población de derecho asciende a 586 personas, de las que 283 son hombres y 303 mujeres.
Hoy no queda nada del castillo mencionado anteriormente, aunque debió de ser muy fuerte para resistir el ataque del Conde de Lara que había asolado previamente otros bienes de Gonzalo Ruiz de Girón y atacado la fortaleza vallisoletana de Montealegre. Los meses de octubre y noviembre de 1217 estuvo preso en la fortaleza Álvaro Núñez de Lara, capturado después de protagonizar, cerca de Herrera de Valdecañas, una fallida emboscada contra el Rey. Su libertad le costó la entrega al monarca de los castillos que poseía y la estancia en prisión hasta su entrega efectiva.
Fuera de su recinto, a la sombra de un solitario olmo corpulento y frondoso, tuvo lugar la ceremonia de proclamación del rey, en cuyas cercanías los vecinos como recuerdo edificaron una ermita, en cuyo interior, según recoge Pascual Madoz a mediados del siglo XIX, había con una lápida con la siguiente inscripción: "En este pueblo y este sitio fue proclamado rey, por primera vez, Don Fernando III, llamado el Santo".
Se conserva en cambio "El Palacio", edificio rectangular de 12,50 metros de largo en la fachada Sur por 9 de ancho, con una altura de 10,50 metros. Está construido con fuertes paredes de ladrillo asentadas sobre una base de sillería, que se divide en tres partes.
En la parte inferior un zócalo que sirve para igualar la altura del terreno; le siguen dos hiladas de 80 centímetros de alto de buena sillería que rodean el edificio; y por último, otras dos filas de piedras de similar altura, con un tamaño superior y que sobresalen ligeramente de las anteriores, que sólo se encuentran en la fachada Norte y esquina Noroeste, salvo en el ángulo Nordeste en que se ve el inicio de una tercera fila donde se alcanzan los 1,50 de altura.
El edificio presenta dos plantas, con una altura máxima de 10,50 metros. El acceso actual se realiza por la planta baja de la fachada Oeste, mientras que los lienzos Norte y Sur presentan en la segunda planta, en el centro de la fachada, sendas aberturas.
Entre los años 2021 y 2022 se realizan obras en el edificio para salvarlo de la ruina y adecuar su uso como ayuntamiento y centro de salud. Para ello se consolida su estructura, se construye una nueva cubierta, se procede a su aislamiento térmico y acústico, y se instala un ascensor y una rampa de acceso entre otras obras. También se procede en el exterior a adecentar el entorno.
Observando el trazado urbano de la localidad se ve que estuvo rodeada por una muralla con forma ovalada. Probablemente tenía cuatro puertas que se abrían a los caminos exteriores. Tan solo queda el recuerdo de la misma en el nombre de las calles Ronda y Puerta Nueva. La primera correspondería a una ronda interior paralela a la muralla, mientras que la de Puerta Nueva hace pensar en una posible ampliación de la muralla y la construcción de una nueva puerta de acceso.
La iglesia parroquial dedica a Santa Eufemia puede estar levantada en el solar que en su día ocupó el castillo. Construida en el siglo XVIII con estilo neoclásico, su esbelta torre de cuatro cuerpos se encuentra separada del resto de la fábrica. En su interior, una única nave que cuenta con cuatro capillas laterales, destacan el retablo mayor barroco, la pila bautismal del XVI, la sillería del coro y su órgano barroco.
Por su término municipal discurre el ramal de Campos del Canal de Castilla.