El origen del asentamiento humano en lo que hoy es Fuenmayor hay que buscarlo en la confluencia de dos ríos, que se juntan en una zona denominada el castillo, en la que parece ser existía un castillo o, al menos, una torre de vigilancia de riegos y, sobre todo, en la existencia de una fuente con abundante caudal (la actual Fuente de los siete caños o de San Juan) de la que tomó su nombre el pueblo (Fuenmayor, apócope de Fuente Mayor).
Precisamente esa torre de riegos es la que se nombra en el testamento de doña Estefanía que en 1066, dona al monasterio de Santa María La Real de Nájera, entre otras posesiones la "turrem venalem de fonte maiorem", expresión latina que puede traducirse al castellano como “torre de riego de Fuente Mayor”
Esta torre vigilancia de riegos puede ser el castillo que se levantaba en el casco antiguo, en donde todavía existen las calles Castillo y Hornos del Castillo, precisamente en la confluencia de los dos ríos que atraviesan Fuenmayor.
Sobre esto se sabe que el 27 de septiembre de 1363, Juan Corboran de Lebet y Juan Vélez de Guevara (hijo de Beltrán Ibáñez de Guevara, Sr. De Oñate y de Dª Urraca Corboran) venden la casa fuerte llamada castillo, con sus dominios, franquicias, privilegios, casas, tierras, etc, así como 27 vasallos, entre ellos Juan López y Juan Martínez clérigos, y Elvira, la gobernadora, al alcalde y los vecinos de Navarrete por 60.000 maravedises
Pero aunque el nombre de Fuenmayor no aparezca en un documento hasta el siglo XII, es de suponer que existiera poblamiento en esta zona incluso antes de la dominación romana, pues estas tierras eran conocidas y citadas en tiempos de los cónsules, según afirma Juan Enrique Merino de Tejada en su obra "Historia de la Muy Noble e Ilustre Villa de Fuenmayor". Dice también que el historiador Silva considera que fue sometida, junto con Nájera y su zona de influencia, en el año 567 por el rey godo Leovigildo.
Se sabe también que el Rey de Nájera Sancho Abarca, que reinó del 970 al 995, mejoró la Villa repoblándola de cristianos, es de suponer que tras conquistarla a los musulmanes.
La fundación de Fuenmayor se pierde en las brumas de la leyenda, ya que dice la tradición que el pueblo lo fundaron tres capitanes de las tropas del Rey Ramiro I que, tras vencer a los musulmanes en la Batalla de Clavijo (844) se asentaron en las tierras del valle que eligieron por su fertilidad y que el rey les concedió. Al menos uno de aquellos capitanes procedía del valle del Baztán, y no sería descabellado pensar que estuvieran relacionados con el Señor de Bazán, marido de doña María Ramírez, fundadora del Hospital de la Orden de San Juan de Acre y que aparece como señora de Fuenmayor en un manuscrito fechado en 1411 que se conserva en nuestro archivo.
Bazán y su derivado Fernández-Bazán ha sido precisamente uno de los apellidos más importantes de Fuenmayor y que en el siglo XVIII nos dará a uno de los más importantes personajes de Fuenmayor, el almirante y ministro D. Antonio Valdés y Fernández Bazán.
En 1363 Fuenmayor era ya una población asentada, que tenía iglesia propia y una cierta población. En ese año, el monasterio de Santa María la Real vende a Navarrete el pueblo de Fuenmayor, con sus 27 vecinos (familias).
Unos años antes, en 1356, se habían unido las dos iglesias, pasando la de Fuenmayor a depender de la de Navarrete que tenía más importancia. Es ese un momento crucial en la historia de Fuenmayor, ya que después costó largos años de pleitos y conflictos la separación de las dos iglesias, que no se hace efectiva hasta 1625, después de muchos litigios en la Chancillería de Valladolid y en el Tribunal Supremo de Castilla y de abonar una importante suma de dinero. También la separación de ambos Concejos o Ayuntamientos fue muy costosa, siendo los propios vecinos de Fuenmayor los que en 1626 compran su "independencia" a Navarrete por 6.600 ducados (un ducado de plata valía 11 reales y la cántara de vino valía unos siete reales, con lo que la separación de Navarrete costó a los vecinos de Fuenmayor más de 10.000 cántaras de vino, lo que nos hace sospechar que ya para entonces Fuenmayor era una villa económicamente próspera).
En 1367 se declara en Castilla la guerra civil y Fuenmayor se alinea en el bando de Enrique de Trastámara que, al ganar la guerra y proclamarse rey de Castilla, le concede privilegios y franquicias y el título de "Villa Libre de Fuero Real" con el dictado de Lealtad.
En 1521, durante la batalla de Pavía, Carlos V derrota al rey francés Francisco I. Un tal Antonio de Leiva, que puede ser natural de Fuenmayor, es quien hace prisionero al rey francés, lo que le supone a la Villa nuevos privilegios.