Notre village a une histoire déjà longue. Dès l'époque romaine, veillant sur la voie de passage qui reliait le plateau de Langres à l’Alsace et à la vallée du Doubs, une tour de guet s'est probablement dressée sur l'éperon rocheux qui domine Auxelles, a précédé la construction du château.
Pour s'opposer aux invasions venues de l'est (IXe et Xe siècles) qui avaient réduit à néant les puissantes abbayes de Luxeuil et de Lure, les fondateurs de la maison de Bourgogne et leurs vassaux les seigneurs de Faucogney étendirent leurs domaines à l'est de la Saône et fortifièrent leurs fiefs. Ainsi s'édifia le château d'Auxelles qui, sur son rocher, occupait une situation privilégiée et constituait avec les châteaux de Passavant et du Rosemont la ligne de forteresses des « trois pucelles ».
Le premier seigneur semble être Ugo de Acella en 1135 ; ses successeurs, les GUILLLAUME & JACQUES & RICHARD, vassaux des Seigneurs de Faucogney, régnèrent sur ACELLA(cité en 1130)-ASCELLA (mentionné en 1156)-AXELLA-AUCELLA (cité en 1221) qui petit à petit devient AUXELLES. Leur lignée s'éteignit entre 1400 et 1427 après la disparition de RICHARD III neveu de l'amiral Jean de Vienne puissant vassal du Duc de Bourgogne.
En 1421, Catherine de Bourgogne, épouse de Léopold III duc d'Autriche qui possède le comté de Ferrette (héritage de Jeanne de Ferrette-Montbéliard)ainsi que la plupart des seigneuries autrichiennes d'Alsace, donne le fief à la dame d'Aigney, dont la famille autorise la prospection de la montagne.