Dans le Haut Moyen Age et jusqu’en 1079, le duché du Haute Lorraine s’étendait au-delà de la chaîne des Vosges en Alsace. En 1070, à la mort du Duc Gérard I dit d’Alsace, une grave querelle s’élève entre ses deux fils, le nouveau Duc Thierry et son frère cadet, Gérard. Pour l’apaiser et après l’intervention de l’Empereur Henri IV, Gérard est doté d’une partie du Xaintois, le Comté de Vaudémont au sens strict (quarante villages environ) et d’une partie du Chaumontois, la châtellerie de Châtel (une trentaine de villages). Le Comté de Vaudémont « l’un des greniers à blé de la Lorraine » entrait dans l’histoire.
Faut-il dater de cette époque la construction du château ou était-elle antérieure comme celle du château de Vaudémont ? Rien ne permet de le préciser. Mais dès 1097, Gérard, premier comte de Vaudémont, et époux d’Helvidis d’Eguisheim – Dagsbourg (petite nièce du pape Saint Léon IX), fonde à proximité, dans la forêt de terne, le prieuré bénédictin de Belval, dédié à la Sainte Croix comme l’était celui de Woffenheim an Alsace dont les Eguisheim avaient la garde. Et c’est à cette époque que les habitants du village de Rancourt, quittent leur coteau, situé plus à l’ouest, pour venir s’établir auprès du château. Deux chartes des évêques de Toul, Henri de Lorraine et Pierre de Brixey marquent pour le milieu de XIIème siècle la chronologie extrême d’un édifice qui bénéficiait sur la voie commerciale, allant de Bâle à Metz, d’une situation plus favorable que celle du château de Vaudémont. Aussi l’atelier monétaire des comtes est-il fixé à Châtel.
Pour mieux préserver leur indépendance, les Vaudémont contractent leurs alliances matrimoniales en Bourgogne, en Champagne et au Luxembourg. Actifs et entreprenants, ils participent aux croisades aux XIIème et XIIIème siècles, puis à la conquête du royaume de Naples avec les Anjou à la fin du XIIIème siècle. Dès la première moitié, du 12ème siècle, ils se font inféoder par l’évêque de Metz de la terre de Chaligny, riches en mines de fer, et ils y édifient un château au milieu du XIIIème siècle. Ils en construisent un autre à Bainville sur la rive gauche de la Moselle, entre Châtel et Nancy.
Entre temps, les difficultés de la succession en Lorraine du Duc Simon II, mort sans enfant en 1206, avaient contraint son neveu et héritier, le Duc Ferry II, à céder aux comtes de Bar la suzeraineté du comté de Vaudémont. Le comte Hugues II leur rend hommage en mars 1218 et son fils Hugues III épouse Marguerite de Bar-Luxembourg. Désormais, les Vaudémont seront des vassaux fidèles et les comtes de Bar leur prêtent des sommes importantes pour agrandir le château de châtel qui leur donne le contrôle de la vallée de la Moselle en aval d’Epinal au détriment du Duc de Lorraine. Le doublement en surface du château aux dépens du village, blotti près de ses murs, suscite alors la création, au pied du prémonitoire et proche du pont sur la Moselle, d’une petite ville, affranchie dès 1317 et dotée d’un hôpital.
Après la mort en Italie des comtes Henri I et Henri II (1278 et 1299), le gouvernement de leur successeur, Henri III, époux d’Isabelle de Lorraine, marque une pause dans le conflit déjà deux fois séculaire. A la mort de leur fils Henry IV, tué à Crécy en 1346, le comté passe à son neveu Henry V de Joinville, fils de Marguerite de Vaudémont, sœur d’Henry IV et petit fils du sénéchal de Champagne, historien de Saint Louis. D’humeur belliqueuse, Henry V entre à nouveau en lutte avec le Duc de Lorraine et laisse en 1366 à sa veuve Marie de Luxembourg une situation financière inextricable qu’elle améliore par une sage gestion.
Leurs fils étant décédés, leurs deux filles partagent les possessions et connaissent de brillantes destinées. L’aînée Marguerite, héritière du comté de Vaudémont et de la seigneurie de Joinville, épouse Jean de Bourgogne, seigneur de Montaigu et d’Amance, puis Pierre comte de Genève, frère du pape Clément VII, et Ferry de Lorraine. Elle est la tige de la seconde maison de Lorraine, puis des empereurs d’Autriche.
Alix, la cadette, de beaucoup plus jeune, a pour sa part les seigneuries de Châtel, Chaligny, Reynel et la Ferté sur Amance. Elle s’unit le 28 avril 1373 à Thiébaut VII de Neufchâtel, neveu de Jean de Bourgogne, premier époux de sa sœur. Thiébaut VII, bon administrateur de ses possessions, part à la croisade en Hongrie contre les Trucs et meurt pour la défense de la foi à Nicopolis en Bulgarie, le 25 septembre 1396. Le frère cadet de Thiébaut VII, Jean II de Neufchâtel, hérita des biens de Jean de Bourgogne, mort sans enfant et il rendra la branche des neufchâtel Montaigu aussi riche et puissante que la branche aînée.