vignette|200px|Blason de Vesoul. vignette|300px|Vesoul en 1881 - Gravure de Charles Barbant à partir d'un dessin de Hubert Clerget.
L'histoire de Vesoul commence au début du Moyen Âge, cependant des traces d'habitat romain et des objets préhistoriques ont été découverts sur le territoire vésulien.
Occupée durant la Préhistoire, la région de Vesoul fut tout d'abord colonisée par les Séquanes, puis par les Burgondes au , avant de changer plusieurs fois de possessions entre différents royaumes. Né au cours du Haut Moyen Âge, Vesoul n'est alors qu'un château fort du nom de Castrum Vesulium, bâti sur la colline de la Motte pour sa situation stratégique. Mentionnée pour la première fois à la fin du , la cité est par la suite érigée en vicomté, appartenant au comté de Bourgogne, et voit un bourg se développer au sein puis au delà des murailles de son château.
Place commerciale et bancaire au , nommée capitale du bailliage d'Amont en 1333, la ville est plusieurs fois pillée lors des conflits de la guerre de Cent Ans et son château détruit en 1595. Rattachée au Saint-Empire romain germanique pendant plusieurs siècles, la ville de Vesoul devient définitivement française en 1678 après la conquête de la Franche-Comté et en profite pour se développer sous le siècle des Lumières.
Désignée comme préfecture de la Haute-Saône après la Révolution, la ville se reconvertit dans les nouvelles industries dès le après avoir été longtemps un centre viticole. Au cours de la deuxième moitié du , la ville devient un site important de la logistique automobile en France, aménage plusieurs zones d'activités à sa périphérie et sa population augmente significativement.
Préhistoire thumb|Outils retrouvés dans la Grotte de la Baume. Objets et fossiles retrouvés Les terres de Vesoul et de la région vésulienne ont offert des vestiges et des traces datant de la Préhistoire, et plus précisément du Néolithique. Les vestiges sont principalement des outils qui ont été fabriqués par ces hommes durant l'Âge de la pierre. Dans la région de Vesoul, l'un des plus anciens monuments retrouvés sur ces terres est le Dolmen de la Pierre-qui-Vire. Doté d'un diamètre de et d'une épaisseur de 40 centimètres, ce monument mégalithique daterait de 3 500 à 3 300 Depuis cette époque, une légende mystérieuse se renferme : la dalle de couverture de la pierre tournerait sur elle-même tous les cent ans. Ce monument très ancien est classé au titre des monuments historiques depuis le 24 août 1976, grâce à l'investigation de la Société d’agriculture, sciences et arts de la Haute-Saône.
thumb|left|Crâne d'Ours des cavernes. Les fouilles sur les hauteurs et plateaux qui entourent Vesoul ont également révélé des traces d'habitats préhistoriques. Au sud de la ville, sur les lieux du Plateau de Cita (site classé Natura 2000) et du Camp de César, (site inscrit à l'inventaire national), les trouvailles de la Commission d'Archéologie de Vesoul ont confirmé que ces deux sites n'étaient pas seulement des camps romains mais étaient également préhistoriqueAlfred Gevrey, Histoire de Vesoul, Partie 1, Livre I, Chapitre , .. Le Plateau de Cita est une colline se trouvant sur les communes de Vesoul, Navenne, et Échenoz-la-Méline. Ce plateau culmine à plus de d'altitude.
Dans les cavités naturelles du Réseau de cavités à rhinolophes de Vesoul, des objets et des ossements d'animaux ont été également retrouvés. Parmi ces cavités, la Grotte de la Baume, qui est située à 2 kilomètres de Vesoul, a permis la découverte d'importants fossiles archéologiques. Les plus importants fossiles retrouvés dans cette cavité sont des crânes et des ossements d'ours. Près de 92 % des fossiles retrouvés dans la Grotte de la Baume proviennent des ours. Les ossements n'ont pas été les seules découvertes dans cette grotte. La présence d'outils lithiques moustérien démontre ainsi une occupation de tous les niveaux du Würm ancien. Dans la partie sud de la grotte, une occupation de l'âge du bronze final III a aussi été prouvée, ..
Antiquité thumb|left|La région de Vesoul situé dans la République des Séquanes.
Premières empreintes d'habitat antique Il y a quelque temps, des objets, des outils et des armes de l'époque gallo-romaine ont été découverts sur les terres de Vesoul. Ces objets antiques ont été principalement retrouvés sur les anciens camps romains du Camp de César, du plateau de Cita et de la colline de la Motte. Sur la Motte, les trouvailles ont été effectuées sur le sommet de la butte et sur ces différents versants des quartiers du Montmarin et Marteroy. Au sommet de la Motte, des objets de l'Antiquité, plus précisément des monnaies et des médailles en l'honneur des premiers empereurs romains ont été trouvés..
À l'époque où les Romains colonisent la Séquanie, ceux-ci furent impressionnés par la topographie du site vésulien. Ces nombreux plateaux et collines apportaient à la ville un aspect défensif et assurant très élevé. À l'époque gallo-romaine, la cité vésulienne est une petite statio. Petit à petit, le début d'urbanisation dans la petite ville de Vesoul se développera et deviendra plus important. Au moment où la France subit de nombreuses invasions barbares, des personnes se sont réfugiées dans ce lieu assuré. La localisation de Vesoul (qui ne possède que quelques habitants) lui permit d'avoir la fonction de gîte d'étape ; en effet Vesoul se trouve entre les grandes voies de communication de la région. Vesoul permettait d'être un relais de poste aux voies Est-Ouest (Mandeure - Port-sur-Saône) et aux voies Nord-Sud (Besançon - Luxeuil). Ces relais à Vesoul des voies de communication continua jusqu'au Moyen Âge. une voie romaine composée de pavé se trouvait blottie au pied de la colline de la Motte..
Durant la période gallo-romaine, les terres de Vesoul font partie du pagus colerensis qui disposait de Corre comme chef-lieu. Au , le pagus colerensis est transféré à Port-Abucin (actuel ville de Port-sur-Saône) et se renomma donc pagus portuensis. Durant la division des contrées en bailliages, Vesoul hérita des terres de Port-sur-SaôneHistoire de Vesoul, Partie 1, Livre I, Chapitre II, : de Alfred Gevrey, 1865. Par la suite le pagus portuensis est supprimé et est remplacé par la vicomté de Vesoul.
Moyen Âge
Haut Moyen Âge thumb|upright=1|Canon retrouvé à la Motte qui était une arme du Castrum Vesulium pour repousser les ennemis
Fondation du Castrum Vesulium La première mention d'une véritable habitation à Vesoul date de 899. Cette mention désigne le Castrum Vesulium, château fort composé d'une large enceinte et de tous les composants que dispose un château fort.
Le château « Castrum Vesulium » est construit sur le sommet de la Motte. Culminant à une altitude maximale de , cette colline est une butte-témoin de calcaire, qui surmonte la vallée du Durgeon. À cette époque de déroulement de longues guerres médiévales, la position du camp offrait une haute importance guerrière car le camp est construit en hauteur. En effet, sa construction sur le sommet de la Motte permettait d'avoir une vision panoramique sur toute la vallée et tous les bas plateaux de la région vésulienne et haut-saônoise.. Le Castrum Vesulium fut édifié par les Comtes de Portois, qui ont fui Port-sur-Saône à cause des nombreuses guerres féodales qui survenaient dans la région de Port.
Le premier siège de la cité L'année 988 est une date historique pour le Castrum Vesulium. Lors de cette année, Vesoul (qui est juste dénommé Castrum Vesulium) connait l'un de ses premiers sièges. Cette invasion fut établie par le duc Henri de Bourgogne ainsi que du comte Lambert de Chalon.
Moyen Âge central thumb|left|Carte schématique des bourgs et villages voisins de Vesoul dans un rayon de deux lieues
Eudes, le vicomte de Beaunes, donna, en 1005, à Saint-Begnigne (avec l'autorisation de Othon-Guillaume et de Robert II de France) une maison avec une vigne et un pré. Cette action marque le début historique de la viticulture à Vesoul. Parallèlement, l'édifice donné par Eudes était localisé in villa Vussilias, ce nom est probablement le dérivé latin du nom de la ville de « Vesoul ». Les premiers édifices d'habitation et de logement à Vesoul sont élevés durant les guerres d'Othon, de Méranie et d'ÉtienneHistoire de Vesoul, Partie 1, Livre I, Chapitre VI, : de Alfred Gevrey, 1865.
Le Castrum Vesulium était dirigé par des vicomtes et des vassaux des comtes de Bourgogne (voir la liste des vicomtes de Vesoul). Othon-Guillaume de Bourgogne pensa certainement que Vesoul détenait une situation géographique importante et stratégique car c'est lui qui en fit le siège d'une vicomté. 1019 est l'année de l'élection du tout premier vicomte du château de Vesoul. Il était nommé Gislebert de Faucogney, cependant Gislebert était parfois nommé Gislebertus suivi de viscomes vesuli castri (vicomte du château de Vesoul)..
Les Romains donnent à Vesoul le nom de Castellum, vers 1030. Ce terme désigne un camp fortifié et non une ville. À cette époque, la topographie et la géologie de Vesoul, entourant le Castrum Vesulium, sont déjà détaillées et précisées dans les ouvrages. L'altitude des pieds de la colline de la Motte était plus basse au qu'à l'époque actuelle. Lors des fortes inondations, ces lieux sont décrits comme un énorme lac entouré de forêts. Les hautes crues des sources d'eau de Vesoul, le Font de Champdamoy et les eaux minérale des Rêpes, ainsi que d'autres sources comme le Durgeon, faisaient des sols de Vesoul un gigantesque marais. Au milieu de ce lac, la colline de la Motte ressortait comme un énorme cône. Cet évènement, qui apparaissait seulement pendant les inondations, donnait l'apparence d'une presqu'île à la colline de la Motte. Alors quasiment inondés, les terrains entourant La Motte obligeaient les gens qui voulaient aller au sommet de la colline de passer par le quartier des Rêpes, au nord de Vesoul. Les Rêpes possèdent des parties de terrain plat contrairement au sud de la ville, qui regorge de plateauxHistoire de Vesoul, partie 1, livre I, chapitre I, et 7 : de Alfred Gevrey, 1865.
L'année 1092 marque la première installation religieuse chrétienne à Vesoul. Cette date représente donc une période importante, puisque la religion va se construire quelque temps plus tard. L'implantation du christianisme à Vesoul est apparue avec l'arrivée des comtes de Portois qui fondent le prieuré Saint-Nicolas de Marteroy..
L'accroissement de la cité
Au , le bourg se développe dans la large enceinte du Castrum Vesulium. Au fil des années, la petite cité devient de plus en plus importante, organisant des marchés agricoles et artisanaux et des foires. Les premiers édifices d'habitation sont élevés à l'intérieur de l'enceinte du château de Vesoul. Possédant une superficie trop faible, l'enceinte du château voit ces maisons se construire en dehors de la fortification. Dotés d'un espace de verdure considérable, les nouveaux habitants de l'extérieur du château vont pratiquer la culture, et surtout celle de la vigne, sur les différents versants de la colline de La Motte.
Le fait d'avoir voulu accroître la démographie et la popularité de la cité fut en partie dû à la difficulté de gravir la Motte, haute de d'altitude et possédant une ascension de plus d'un kilomètre. Les deux autres raisons essentielles pour avoir quitté les fortifications : l'eau devenait de plus en plus rare et la population augmentait considérablement. Durant le , la ville possède la fonction de siège de la justice seigneuriale..
Le premier prévôt de Vesoul, Lambert de Montbozon, est déclaré dans un acte de 1188. La fonction de prévôt était héréditaire et apportée en possession à son propriétaire, selon la coutume féodale..