No obstante no existen datos documentados de su creación como pueblo. El historiador Colmenares supone que la fundación de este pueblo fue en tiempos de Abderramán I de Córdoba, quien vino contra la ciudad de Segovia destruyéndola y haciendo huir a sus habitantes, algunos de los cuales, construyeron en la sierra algunas habitaciones o Palacios que llamaron Palazuelos. A lo que se llamaba Palacios en tiempo de la Repoblación eran normalmente piezas sueltas de una misma vivienda o incluso solares de escaso significado. En época medieval Palazuelos de Eresma era mentado como Palaçuelos (primera mención conocida: 1247), perteneciendo a su entorno un buen número de poblados de los cuales solo se conserva el nombre como son los de Pellejeros, Rosales, San Bartolomé y Torrecilla. A partir del Siglo XVIII se añade a Plazuelos de Eresma la segunda parte de su nombre haciendo referencia al Río Eresma.
En el siglo XVI, una familia de origen italiano apellidada Fabio, se asentó en Palazuelos, estableciendo una industria papelera, la cual llegó a tener gran importancia en el panorama de la industria española. El Rey Carlos II decretó que se gastase el papel que de ésta salía en las secretarías del Estado, con lo que tomó gran impulso la fabricación.