Aparece mencionada por primera vez en el año 974, en el Códice donde se encuentra el Índice de Dueñas, con el nombre de "Fuentes de Don Bermudo". En 1129 Alfonso VII cambia con el monasterio de San Zoilo, de Carrión de los Condes, varias localidades por el término de Fuentes.

Más tarde, a mediados del siglo XIV, por el Becerro de los Beneficios de la Catedral de Palencia, se sabe que la localidad contaba con las iglesias de San Pelayo, San Román, San Miguel, San Pedro y Santa María, de las que únicamente se conservan las dos últimas y la ermita de San Miguel.

El Libro de las Behetrías, confeccionado en esa época, indica que es lugar de behetría de D. Juan Alfonso y figuran como señores naturales los Lara, Girón, Tello y Vizcaya, considerando a estos últimos descendientes de su fundador. Pagan al rey impuestos por martiniega, servicios y monedas, mientras que D. Juan Alfonso como señor recibe 180 maravedís por martiniega y D. Nuño 30 maravedís por la heredad que allí tiene y martiniega. También recibe cada uno de los señores naturales 6 maravedís.

Se sabe que en 1514 el importe de las alcabalas asciende a 195.59 maravedís, cantidad únicamente superada en la merindad de Campos por la capital palentina y Frechilla.

Durante el levantamiento comunero gentes de esta villa participan, junto con hombres de Palencia y Becerril de Campos, en el asalto llevado a cabo en los primeros días de enero de 1521 a la Audiencia del Adelantamiento de Castilla situada en la vecina localidad de Frechilla.

Días antes de la batalla de Villalar, suministra los víveres y pertrechos solicitados por el ejército imperial a su paso por la villa, en un intento de congraciarse con el Condestable y evitar sanciones posteriores. No obstante, más tarde tuvo que pagar 300 ducados de oro como contribución de guerra.

Poco después, en 1528, la localidad cuenta con 384 vecinos pecheros que pagan en concepto de Servicio 103.970 maravedís. En el censo de 1591 el número de pecheros ha ascendido a 498, además de 17 que pertenecen al clero secular, para una población total de 515 vecinos.

En la primera década del siglo XVII el rey Felipe IV vende al Duque de Lerma varios pueblos de behetría entre los que se encuentra Fuentes de Nava, uno de los de mayor vecindario de la comarca de Campos.

La localidad cuenta con 462 vecinos cuando en 1608 el Duque de Lerma adquiere las alcabalas y tercias de la villa, aunque más tarde, en 1626, pasan de nuevo a la Real Hacienda, para ser vendidas dos años después a varios hombres de negocios.

Tras el fallecimiento de Diego Gómez de Sandoval, último duque de la casa de Lerma, pasa el señorío a sus sucesores los duques de Medinaceli. Poco después, en 1631, se censan 1.168 personas, contabilizadas como 344 vecinos que junto con las 4.252 cabezas de ganado menor que existen consumen anualmente 206 fanegas de sal. En el censo de 1646 aparece con 272 vecinos, que disminuyen a 215 en el de 1712, distribuidos en 76 vecinos, 38 viudas consideradas como 19 vecinos y 120 pobres. Además hay 10 mendicantes que no se les considera vecinos.

Según los datos del Catastro de Ense­nada confeccionado en 1751 Fuentes es señorío de los duques de Medinaceli y tiene un vecindario formado por 447 vecinos y medio, contando cada dos viudas como un vecino, además de 16 eclesiásticos. El caserío lo forman 451 casas, incluidas 6 destinadas a vivienda para pobres; de las que 447 son habitables y 4 se encuentran inhabitables por su estado ruinoso. Asimismo hay 15 casas de las que únicamente queda el solar.

En 1768 dispone de 1.939 habitantes, repartidos entre los 1.039 que tiene la parroquia de Santa María y los 900 de la de San Pedro. Por esas fechas se sabe de la existencia de 9 cofradías en la localidad, siendo la de la Cruz la más importante.

Poco después, en el año 1787, la población censa 2.082 habitantes, de los que 977 son hombres y 1.105 mujeres. Con ocupación específica encontramos 168 jornaleros, 103 labradores, 50 criados, 44 fabricantes, 36 artesanos, 12 militares, 11 estudiantes, 4 comer­ciantes, y 3 escribanos. Relacionados con la iglesia hay 11 beneficiados, 5 de la orden tercera del patrimonio, 4 sacristanes, 2 tenientes de cura, 2 de órdenes de menores y 2 dependientes de la inquisición.

No están incluidos en el censo el en­fermero, la enfermera y los 2 empleados que atienden el hospital de la Santísima Trinidad, ni los 11 hombres, 26 mujeres 5 niños y 3 niñas que se reparten entre las cuatro casas que forman la Casa de Misericordia.

Sebastián Miñano informa en 1828 de una población formada por 3.065 habitantes, considerados como 681 vecinos, con una producción de 35.000 cántaras de vino "que es de lo mejor de toda la tierra de Campos".

Por su parte Pascual Madoz a mediados de siglo indica que la villa tiene 2.372 per­sonas, equivalentes a 480 vecinos, y un casco urbano con 480 casas, una "mala cárcel" y escuela de primeras letras a la que asisten 170 niños y 40 niñas. También informa de la existencia de un molino de viento para uso industrial.

Con 2.390 habitantes, 556 casas y 26 cuevas, se la menciona en 1874, mientras que en 1883 se indican 2.025 habitantes, 646 casas con muchas de construcción moderna, un reducido hospital en malas condiciones por falta de recursos y tres escuelas para niños, niñas y párvulos que atienden de 240 a 250 alumnos.

En 1888 la villa cuenta con una población de derecho de 2.118 personas, con 71 edificios de una planta, 453 de dos, 50 de tres o más y 107 albergues (barracas, cuevas, chozas)

De la muralla que en otro tiempo rodeaba la localidad únicamente se conserva una puerta del siglo XV, conocida como Postigo de la Virgen, en cuya parte superior una pequeña habitación con balconada abierta al interior de la población da cobijo a la Virgen del Postigo, a la que se encomendaban viajeros y emba­razadas. En la viga que da al exterior aún se puede apreciar el quicio superior de la puerta.

Se ubica en la plaza Corro Postigo, en la que también desemboca la calle Postigo, y cuyos nombres al igual que el de la calle de Cercas de Vega han quedado como recuerdo de la muralla. Hasta 1907 también aparecen referencias a otra calle denominada las Cercas.

Al igual que en los pueblos de los alrededores, la cerca estaba formada por un grueso muro de tapial, lo que explica los escasos restos que se han conservado de la misma.

En la población destaca la iglesia de San Pedro de finales del siglo XV, principios del XVI, con una torre renacentista del XVI de 65 metros de altura rematada con una espléndida balaustrada y linterna hexagonal, apodada la "Estrella de Campos". En su interior destaca el Retablo Mayor y órgano de Tadeo Ortega de 1785.

También de este siglo es la iglesia de Santa María, recientemente restaurada, de­cla­rada Monumento Nacional en 1978, con una bella portada gótica. Es una de las cinco sedes del museo territorial Campos del Renacimiento. En el interior destaca el impre­sionante artesonado mudéjar policromado y un segundo órgano barroco de Tadeo Ortega, de 1790. Junto a la iglesia se encuentra el campanario, con aspecto más bien de torreón-fortaleza.

Cercana a esta iglesia se encuentra la capilla de la Vera Cruz; mientras que en el corro del Postigo está el humilladero de la Virgen del Postigo, y fuera de la localidad, junto al cementerio, la ermita de San Miguel, del XVII.

Destacar asimismo dos casas palacio del siglo XVII en la plaza Calvo Sotelo, y varias casas en la calle Mayor y plaza Marqués de Estella, de los siglos XVII a XIX.

Cruza su término municipal el ramal de Campos del Canal de Castilla cuyas aguas se usan, en ocasiones, para inundar la laguna de la Nava, uno de los humedales más importantes de la región cuyo centro de interpretación se encuentra en la localidad.