Aunque no haya constancia escrita, sí se tiene en cuenta la Via Romana, que partía de Calagurris Iulia (Calahorra) y que llegaba a Grávalos siguiendo el curso del Río Cidacos, por lo que deducimos que pasaba por Autol.
El hallazgo de cerámica Celtibérica, en Noviembre de 1994, a los pies del castillo de Autol, hace remontar nuestra historia (de forma fehaciente) hasta el siglo VI antes de Cristo. Este hallazgo corrobora el precioso valor estratégico de nuestro Castillo, cuyos actuales restos (probablemente árabes) no sean sino una reconstrucción sobre un antiquísimo asentamiento militar que vigilaba el estrecho desfiladero, por el que discurría el Río Cidacos y la Vía Romana, a cuyo amparo se formó un núcleo de población.
Precisamente, a orillas de nuestro río y en nuestro pueblo, tuvo lugar la batalla de Tseima, en el año 843, en la que Muza, gobernador de Zaragoza, aliado con el rey cristiano de Navarra, venció a las tropas del Califa de Córdoba, Abderramán, contra el que se había rebelado.
En el año 939, aparece por primera vez Autol en un texto escrito, con el nombre de Abtole. El Conde Fernán González hace un voto de Ofrenda Perpetua a San Millán de La Cogolla si, por su intercesión, vencía al califa de Córdoba, Abderramán III. El califa cayó derrotado en la famosa Batalla de Simancas, por la que se redactó la Escritura de Privilegio de Voto a San Millán, por el cual los pobladores de Abtole, y pueblos limítrofes, se comprometían a ofrecer al Santo una media de vino y un pan, por cada casa. Con los avatares de las guerras y por su situación geográfica fronteriza, Autol pasó de un reino a otro. Así, perteneció a Navarra hasta el año 1076 en que pasó a poder de Castilla y en 1115 al Reino de Aragón, hasta 1134.
Tras varios cambios de dominador, queda definitivamente incorporado a Castilla en 1176. Decisión de Enrique de Inglaterra, que había sido nombrado juez para solucionar la reclamación del Castillo de Autol a Sancho VI de Navarra, por parte de Alfonso VIII, rey de Castilla. De ahí la presencia del león rampante empuñando un mandoble que figura en el escudo, representando el arbitraje del Rey de Inglaterra. El Castillo de Autol fue uno de los cuatro que Don Jaime de Aragón entregó a Don Alonso Lopez de Haro en el año 1262.
El Rey Enrique II de Castilla (1369-1379) cedió el Castillo y el Señorío de Autol a Don Pedro Ximénez de Arnedo, como recompensa a su valor y ayuda en el campo de batalla, en su disputa por el Reino, contra su hermano Don Pedro I El Cruel. Así, además de ser jefe de la Guardia del Rey, se convirtió en el primer Señor de Autol. Y como tal señorío ha permanecido entrocado a esta familia, en la que ha predominado el apellido Puelles (hasta su desaparición en el siglo XIX, ya que en 1837 desaparecen en españa todos los señoríos).
El Condado de Autol aparece en 1893 cuando Don Joaquín Garralda Oñate, Senador Vitalicio y Capitán de La Armada Real, recibió dicho título por Real Orden, y con carácter hereditario.