Los primeros datos escritos que nos hablan de la villa son de mediados del siglo XII, pero parece ser que el municipio fue repoblado con anterioridad por algunas tribus de la zona donde estaban asentados los vascones o los astures. Junto a éstos, también había noticias de civilizaciones romanas y visigodas.

La leyenda dice que el pueblo debe su nombre a Don Pelayo, el rey astur iniciador de la Reconquista. Según el relato, Don Pelayo bajó hasta el término donde ahora se ubica el municipio y mandó cavar un pozo para saciar su sed y la de sus ejércitos. Junto a esta fuente se creó un campamento alrededor del cual se formó Fuentepelayo.

Fuentepelayo no ha sido siempre un pueblo con autonomía propia, a principios del milenio perteneció a la cercana villa de Cuéllar para posteriormente pasar a depender del Obispado de Segovia en 1181.

Fuentepelayo siempre ha estado ligado a la monarquía. Esta unión se puso de manifiesto en 1277 cuando Alfonso X el Sabio concedió privilegios a su concejo como villa del obispado de Segovia. Catorce años después, en 1291, Sancho IV solucionó una demanda en favor de los vasallos de Fuentepelayo, los cuales le solicitaban estar exentos del tributo de Acémilas y Fonsaderas.

Continuó con jurisdicción del obispado hasta que Felipe II, que necesitaba dinero para pagar las campañas de Flandes, con la bula del Papa Gregorio XIII, vendió la localidad en subasta y se la concedió a uno de sus coroneles, Don Alonso López Gallo, en el año 1589.

Durante este año el censo mostraba una población de 430 habitantes. La venta de la villa ascendía a 7.070187 maravedíes. Antes de hacerse definitiva esta operación, Felipe II dio la oportunidad al propio vecindario de comprar la villa por la misma cantidad que ofreciera Gómez Gallo, pero no hubo ningún interesado o los que había no llegaban a la cantidad solicitada. En el escudo de Fuentepelayo aparece un gallo como alusión a esta venta y al apellido del comprador......

El pueblo fue una de los pocos de la provincia en el que se levantó un Rollo, lo que demuestra la importancia que tenía Fuentepelayo hace unos siglos. El rollo era símbolo de soberanía y jurisdicción, y representaba el concepto de soberanía autónoma en lo jurisdiccional por parte de la localidad que lo exhibía, y que tenía por tanto el título de villa.