En pleine guerre de Dix ans, Louis XIII décide de renforcer les places fortes stratégiques le long des frontières. Auxonne est un point de passage obligé pour entrer dans le royaume. Un ouvrage fortifié (demi-lune ou redan) est construit vers 1636 sur le front est de la cité, dans l'alignement de celui du Comté. Appelé Notre-Dame pour rappeler la porte de ville située près de ce bastion et murée en 1636, il sera nommé bastion de Kehl par la suite, en référence au pont de Kehl construit par Vauban près de Strasbourg . Lorsque Vauban reprend le chantier des fortifications de la ville en 1679 après la mort du comte d'Aspremont, le bastion est loin d'être achevé. L'ingénieur demande qu'on "achève le terre plein", de faire les parapets à l'épreuve du canon, de curer et nettoyer les fossés, d'installer une batterie en "barbe" à sa pointe et de "relever le vieux mur de sa gorge pour luy pouvoir servir de retranchement au besoing". Gorge et flancs s'appuient sur l’enceinte médiévale. En 1840, une note rédigée par le service du Génie (direction de Besançon) propose d’améliorer le front de Kehl en ajoutant une tenaille entre le bastion et celui de Comté. Une demi-lune est également projetée, intercalée entre lui et celui du Moineau, qui sera probablement transformée en lunette dans la liste des projets pour 1861-1862. En 1881, un plan indique que le bastion dispose de "quatre traverses-abris voûtées en maçonnerie".

Le déclassement d'Auxonne amène sa démolition en 1905 pour favoriser une extension urbaine avec la création du Quartier Neuf, zone pavillonnaire et de faubourgs maraîchers.