Aunque el topónimo "nava", es indicativo de un posible asentamiento prerromano, la primera mención histórica a Navasfrías data de 1219, cuando el monarca leonés Alfonso IX dona este lugar a la ordende Alcántara dentro de la dinámica repobladora, y le señala como término una legua alrededor. Posteriormente el propio monarca aprobará el fuero que le concede la orden a nuestro pueblo en el año 1226.
            Pertenecía Navasfrías al término de Sabugal cuando este aún no había pasado a la corona portuguesa.Como  territorio de frontera vivió nuestro pueblo durante muchos siglos aislada, olvidada y castigada.
            En 1235 ya se constata la existencia en Navasfrías de una iglesia bajo la advocación a S.Juan. Los años que van hasta 1297 con la firma del tratado de Alcañices son de gran  penuria para el pueblo que a mediados de siglo queda despoblado por el asedio al que lo someten  los portugueses con constantes robos y saqueos. Sin embargo la Orden a la que pertenece decide repoblarlo y pocos años después Navasfrías queda integrado dentro de la Encomienda de Salvaleón (antigua villa  al sur de Valverde) junto a Valverde del Fresno  y el poblado de la Genestosa. A partir de este momento es poco conocida la historia de nuestra villa, poco tiempo después pasará a formar parte de la Encomienda de Eljas que después de unificada a  Salvaleón inicia su preeminencia en la zona. A lo largo de todo este tiempo continúan las rencillas con Portugal, y tanto portugueses como castellanos penetran a uno y otro lado de la frontera con intereses similares: el saqueo, el robo y destrucción del enemigo. Las penurias y depresión de la zona continuaron varios siglos en toda esta comarca y en época de los Reyes Católicos conocemos como dicha zona era una de las más degradadas de toda la actual provincia salmantina. En este tiempo destaca la figura de Hernán Centeno, el cual se hizo construir un castillo a pocos kilómetros de nuestro actual pueblo (lugar hoy conocido como las Torres junto al Espinazo) y desde el cual se lanzó sobre los castillos de Trevejo y Eljas que ocupó durante varios años, por estos hechos y por otros de tal calibre fue conocido en estas tierras como el Travieso.
            En el año 1617 el duque de Tursi, rector de la universidad de Salamanca donó al pueblo una cruz parroquial de plata. En este siglo nuestra tierra conocerá de nuevo los enfrentamientos con Portugal durante la guerra de Secesión que desde 1640 a 1668 afectó a toda la frontera con el país vecino. Durante este período tienen lugar en nuestro pueblo hechos bélicos de gran trascendencia así como expediciones de saqueo a diferentes pueblos del vecino Portugal. Sin haberse recuperado la zona de todos estos enfrentamientos, comenzará la guerra de Sucesión de la corona española, que de nuevo nos enfrenta a Portugal, las correrías son de nuevo numerosas y en este tiempo debió quedar despoblado el lugar de La Genestosa que hasta entonces había sido una villa cercana a Navasfrías y hoy apenas existe rastro de ella.Durante todo este tiempo continuó la villa perteneciendo a la Orden de Alcántara y es más que probable que sufriera más de una despoblación casi total debido a los constantes enfrentamientos con Portugal pues su población apenas creció a lo largo de varios siglos: Así en 1571 Navasfrías tan solo tenía 10 vecinos (que no habitantes cada vecino implica una unidad familiar, por lo que podemos deducir del orden de 40-50 habitantes). En 1591 cifra alcanza los 41 vecinos(+-200 habitantes). 1619 se conservaba esa cifra en torno a los 40 vecinos, hasta mediados del siglo siguiente  volvemos a tener datos poblacionales. En 1749 la ci se sitúa en 49 vecinos (lo que supone un crecimie nulo con respecto a las cifras anteriores si bien cierto que el no tener relación del numero de vecinos durante más de un siglo hace que no podamos conocer si albergó mayor numero en épocas anteriores),en 1787 y hablando no ya de vecinos sino de habitantes tenemos una cifra de 285 lo que apenas supone un crecimiento muy significativo, sin embargo en 1791 la cifra es de 90 vecinos lo que equivale a más de 350 habitantes. El crecimiento por tanto es evidente como lo acentúan las cifras de 1850 recogidas de Pascual Madoz que nos da unas cifras de 190 vecinos o lo que es lo mismo alrededor de 820 habitantes. Ya a comienzos del siglo XX se sobrepasa la barrera de los 1000 habs., concretamente Navasfrías tenía 1459 habitantes para pasar en 1950 a los 2106 iniciando a partir de ese momento un declive hasta los pocos +-700 de que goza en la actualidad.A  finales del siglo XVIII nuestro pueblo deja de pertenecer a la orden de Alcántara. Por estas fechas comienza la construcción de la actual iglesia parroquial que bien pudo construirse sobre otra destruida y arruinada por las frecuentes guerras que tuvo que soportar la comarca o por necesidades de espacio ante el incremento de la población. A comienzos del siglo siguiente la Guerra de la Independencia y las correrías de liberales contra absolutistas volvieron a tener como escenario a nuestro pueblo y los alrededores. En 1833 se hizo la actual división provincial y Navasfrías que había pertenecido a Cáceres pasa a formar parte de Salamanca. Como hecho significativo y aclaratorio de hasta que punto  estaba aislada esta zona del resto, hay que señalar  que la comarca de El Rebollar a la que pertenece Navasfrías en la actualidad fue comparada a principios del presente siglo con la miseria en la que vivían los habitantes de las Hurdes, de sobra conocida por las visitas que realizó el monarca Alfonso XIII, y por reportajes cinematográficos como el que realizó Luis Buñuel y titulado "Las Hurdes: Tierra sin pan Por último hay que destacar que en nuestro pueblo a lo largo de la historia residieron varios nobles de cierto renombre y a comienzos de este siglo hay que destacar la presencia en Navasfrías de Matias GarcíaAzabeño el cura-poeta que pasó varios años en nuestro pueblo y al cual le debemos varios poemas en los que describe los paisajes navasfrieños.