La "Factella" de época medieval aparece mencionada por primera vez, de forma indirecta, en un documento en el Becerro I de Sahagún del año 989, donde también se encuentra el primer documento que habla directamente de la localidad, fechado en 1048. Sin embargo, su origen es anterior como lo atestiguan los restos aparecidos en su término municipal, principalmente de época romana, aunque también hay algunos de la Edad del Bronce.

Frechilla fue lugar de Behetría natural, y así consta en el Becerro de las Behetrías de 1352, pagando al rey martiniega y montazgo, pero no fonsadera. En 1489 aparece como señor Don Fadrique Enriquez, Almirante de Castilla. Las alcabalas cobradas en 1514 ascendieron a 217.140 maravedis.

A primeros de enero 1521, un capitán del ejército de Acuña al frente de 300 hombres, asaltó la localidad con la intención de capturar al Licenciado Francisco de Lerma, Alcalde Mayor del Adelantamiento de Campos, apresando a su esposa y criados al haber huido éste. Meses más tarde, en vísperas de la batalla de Villalar, suministró al igual que otras poblaciones de la comarca, víveres al ejército imperial al mando del Condestable de Castilla, con el fin de ganarse su favor y evitar mayores contribuciones de guerra.

En 1592, Felipe II otorga el señorío de esta villa y la vecina Villarramiel, así como el título de Marqués de Frechilla, a su sobrino Duarte de Braganza, segundo hijo de su prima Catalina, en cumplimiento de una promesa hecha en el momento de la toma de posesión como rey de Portugal.

De la antigua cerca que rodeaba la villa, hoy tan sólo queda su recuerdo. Construida con grueso tapial, como otras del entorno, se conservó en su mayor parte hasta 1836. Se accedía a su interior a través de cuatro puertas: denominadas San Miguel la situada al Norte, Santa María la del Sur; mientras que al Oeste estaban la de Mediavilla y de la Calle Mayor, así como el portillo de San Juan.

Era una muralla más para protegerse de bandidos o pequeños ataques que a prueba de ejércitos. Así, dos meses después de la batalla de Villalar, sirvió para detener a un grupo de antiguos comuneros que al enterarse de la presencia en Frechilla del Condestable de Castilla, se dirigió a la villa con las peores intenciones. En cambio, como se ha indicado anteriormente, no detuvo el asalto realizado a primeros de ese mismo año por el ejército comunero.

Tampoco resistió la acometida, en 1217, del ejército de Alvar Núñez, conde de Lara, que tras levantar el cerco de Autillo de Campos, donde se encontraba doña Berenguela, se dirigió a Frechilla donde destruyó la casa fuerte que tenía su enemigo, el mayordomo de la reina, Gonzalo Ruiz de Girón.

Lo que hoy vemos de su imponente iglesia de Santa María corresponde a las obras de los siglos XVII y XVIII pues en 1533 sufrió un incendio. Cerca del pueblo, a un kilómetro, se encuentra la ermita barroca de San Miguel, del siglo XVII.