L'origine du nom de Navenne semble provenir du celtique naven qui signifie "pied de coteau"

Au Moyen Age Navenne comprenait le village ancien sur son emplacement actuel et plusieurs hameaux tels que ceux de Graisse, du Pont avec son église et d'Itac.
Au 14ème siècle les seigneuries de Navenne et de Graisse faisaient partie du domaine des comtes de Bourgogne. En 1789 elles appartenaient à la famille de Lampinet et furent intégrées en 1790 aux districts et cantons de Vesoul.
Le territoire de Navenne s'étendait jusqu'au Durgeon et se trouvait limitrophe des communes Noidans les Vesoul et de Frotey les Vesoul. La gare de Vesoul, tout comme la manufacture des tabacs (maintenant Maison des associations rue Jean Jaures) étaient jadis implantées sur Navenne. Mais par deux fois, en 1860 et en1876 Navenne subit de la part de Vesoul, interessée par les taxes d'octroi, des amputations territoriales qui devaient porter les limites communales avec Vesoul à la rue de la Tuilerie (actuellement rue Pierre Curie) et à la rue de Villersexel.

Les habitants de Navenne se consacraient essentiellement à la culture de la vigne et au maraîchage.

L'église avec son toit à l'impériale date de 1783. Le château seigneurial, situé au haut du village (actuellement 31 rue Victor Hugo) abrita l'école de garçons et de filles et la Mairie jusqu'en 1954 et puis, jusqu'en 1978, un peloton de gendarmerie motorisée.
Un château, construit au 19ème siècle et détruit en 1991 occupa l'emplacement de l'actuel Centre de Réeducation Fonctionnelle ; il servit pendant quelques années d'annexe à l'hôpital Paul Morel de Vesoul. Le cimetière militaire fut aménagé au lendemain de la seconde guerre mondiale.

Navenne se développa dans les années 1930 avec les lotissements Bouvaist (actuelles rues F.Buisson, Joffre, Foch) et Melk (bas de l'actuelle rue Général de Gaulle), 1960 (quartier rue Maurice Gillot) et 1980 'Montmartine). D'autres aménagements, maisons individuelles et commerces, équipements publics (Centre de Gaulle, Gymnase) virent le jour depuis lors.

Navenne appartient à l'arrondissement de Vesoul, au canton de Vesoul Est, à la communauté de communes de l'agglomération de Vesoul(CCAV) et au Pays de Vesoul/Val de Saone.

Selon les sources Insee la population (sans doubles comptes) de Navenne est passée de 1195 habitants en 1962 à 1641 en 1999. La population totale en 1999 a été de 1781 habitants.

La très grande majorité des résidences principales soit 79,1% est constituée de maisons individuelles et 68 % des habitants sont propriétaires de leur logement.

Les municipalités qui se sont succédé ont contribué à une urbanisation équilibrée alliant qualité de l'environnement et esthétique.
En outre elles ont veillé à l'adéquation des équipements scolaires aux besoins par l'ouverture de nouvelles classes, soutenu la création du centre de loisirs sans hébergement, crée des équipements sportifs (gymnase, plateau sportif ...), des salles de réunion (Centre de Gaulle), une bibliothèque, en liaison avec le centre de rééducation fonctionnelle. Un important programme d'amélioration de la voirie inspiré par des objectifs de sécurité routière et d'embellissement (enfouissement des réseaux électriques et téléphoniques) est en cours.
Navenne niché dans un écrin de verdure se doit de contribuer à la protection de l'environnement, de son eau potable (périmètre de sources, remplacement des canalisations en plomb). Par ailleurs le patrimoine forestier communal est parcouru de sentiers de promenades piétons et VTT conduisant notamment aux plateaux de Cita et de Cassini ; un sentier botanique ( arboretum) présente de nombreuses essences sylvicoles.

Navenne est bien équipée en centres commerciaux, commerces de détail, artisans, cabinet médical, pharmacie, laboratoire d'analyses et ses habitants peuvent bénéficier des nombreux services mis en place par la communauté de communes de Vesoul (transports, loisirs, collecte des déchets en porte à porte avec tri sélectif, cyberbase, ludolac). Elle accueille également deux importantes structures consacrées, l'une à la formation (AFPA) et l'autre à la santé (Centre de Rééducation Fonctionnelle).