No es muy conocido el origen del nombre de Alaejos. Unos dicen que en un principio se llamó «Ararejos», puesto por alguno de nuestros reyes godos, ya por haber tomado parte en su erección, como por haber formado de sus valientes y bravos vecinos una legión alada, a la que, por muy querida, puso este apellido.
Otros creen, aunque sin asegurarlo, si será esta villa la que con el nombre de «Alexameo» cita el memorial de la Historia de la Nación que envió Don Alfonso IV, padre del rey Don Ramiro, a Don Sebastián, obispo de Salamanca, en la cual enumeraba las conquistas que emprendió Alfonso I del lado meridional del río Duero, y dice: Que ganó en ellas, a excepción de los castillos, muchas ciudades que estaban tiranizadas y en poder de los moros, entre las cuales cuenta a Salamanca, Ledesma y Alexameo. Por tener esta última bastante alusión con la nuestra, se cree si será ella, ya que el teatro de la guerra fué el terreno mismo en que se sitúa.
Se atribuye su fundación a uno de los primeros reyes de Asturias, y éste se cree sea Alfonso III el Magno.