El topónimo nava es de origen prerromano y significa tierra llana rodeada de colinas. Surgida en el ámbito de la repoblación medieval en torno a los siglos X y XI, su época de mayor esplendor se sitúa entre los siglos XVI y XVIII. Es entonces cuando Nava de Roa se beneficia de ser un nudo de comunicaciones, cruce de los caminos Valladolid-Soria y Segovia-Zaragoza.
Cuando en el año 1143 Alfonso VII concede el fuero de Sepúlveda, surge la Comunidad de Villa y Tierra de Roa, siendo una de sus 33 aldeas.
En el Censo de Vecindarios de la Corona de Castilla realizado en 1591 se denominada Nava, pertenecía a la Tierra de Roa, incluida en la provincia de Burgos. La comunidad contaba con 1.569 vecinos pecheros, correspondiendo 563 a la capital.
Lugar perteneciente a la Tierra de Roa con jurisdicción de señorío ejercida por el Duque de Siruelo quien nombraba su regidor pedáneo.
A la caída del Antiguo Régimen queda constiuido en ayuntamiento constitucional en el partido de Roa, perteneciente a la región de Castilla la Vieja que en el Censo de 1842 contaba con 186 hogares y 605 vecinos.
El siglo XIX marcó el declive sobre todo por dos hechos destacados. El primero fue su destrucción total (1836) en el marco de la Primera Guerra Carlista por el general carlista Miguel Gómez Damas. El segundo fue la plaga de filoxera que acabó con los viñedos de la zona y, por lo tanto, con gran parte de su actividad económica. El descenso de población hasta nuestros días ha sido continuo.
En esta población se mantuvo encarcelado a Juan Martín El Empecinado, famoso guerrillero que luchó contra las tropas napoleónicas, tras su captura en Olmos de Peñafiel (1823). Posteriormente fue entregado al alcalde de Roa de Duero, Gregorio González, y allí fue ejecutado en 1824.