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 era lugar de behetría de Juan Alfonso, figurando como señores naturales las casas de Lara, Girón, Tello y Vizcaya, considerada esta última como descendiente de su fundador. Pagaban al rey impuestos por martiniega, servicios y monedas, mientras que Juan Alfonso como señor recibía 180 maravedís por martiniega y D. Nuño 30 maravedís por la heredad que tenía allí y martiniega. También recibía cada uno de los naturales 6 maravedís.

En 1514 el importe de las alcabalas ascendía a 195.59 maravedís.

Durante el levantamiento comunero gentes de esta villa participaron, 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 que se encontraba situada en la vecina localidad de Frechilla.

Días antes de la batalla de Villalar, suministró los víveres y pertrechos solicitados por el ejército imperial a su paso por el pueblo, en un intento de congraciarse con el Condestable y tratando de 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 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 pertenecientes 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 encontraba Fuentes de Nava, uno de los de mayor vecindario de la comarca de Campos.

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

Tras el fallecimiento del último duque de la casa de Lerma, Diego Gómez de Sandoval, pasa el señorío a sus sucesores, los duques de Medinaceli, en cuyo poder esta en 1751 cuando se realiza el Catastro de Ensenada. El vecindario estaba formado por 447 vecinos y medio, contando dos viudas como un vecino, además de 15 eclesiásticos. El caserío lo formaban 451 casas, incluidas 6 destinadas a vivienda para pobres, de las que 447 son habitables, 4 en estado ruinoso y por lo tanto inhabitables, y 15 de las que únicamente quedaba el solar.

Un siglo más tarde el número de casas asciende a 480, mientras que el vecindario lo formaban 456 vecinos, 2.372 almas. Contaba con escuela de primeras letras a la que asistían 170 niños y 40 niñas.

Poco después la población de hecho desciende a las 2.025 personas que figuran en el censo de 1877, 1.011 hombres y 1.014 mujeres.

Como recuerdo de la muralla que en el siglo XV rodeaba la localidad únicamente se conserva la puerta 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. La cerca, al igual que las de los pueblos cercanos, 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, declarada Monumento Nacional en 1978, con una bella portada gótica. Destaca en el interior el impresionante 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.