La construction du bastion est antérieure aux travaux engagés en 1673 par le comte d'Aspremont. Il doit son nom à la présence d'un moineau (ou caponnière) situé à sa gorge, ouvrage bas adossé à un mur d'escarpe défilant le fossé. Le moineau, ici, correspondait à un batardeau en travers du fossé alimenté par le cours d'eau nommé la Brizotte. Le bastion est détaché du mur de l’enceinte médiévale comme le montre un plan datant de 1638. A cette date, l'ouvrage est en cours de construction, de même qu'un moulin proche.

En 1673, d'Aspremont conserve l'implantation du bastion dans son projet, comme un ouvrage extérieur ou un dehors retranché à l'image d'une demi-lune. En janvier 1679, Vauban poursuit les travaux des fortifications de la ville. Dans son mémoire relatant l'état d'avancement du chantier, il note qu'il est urgent d'achever le bastion en faisant le terre-plein pour accueillir une batterie en "barbe", en creusant le fossé par devant et en faisant des rampes. A l'instar de son prédécesseur, il n'envisage pas de bâtir une courtine sur les flancs du bastion mais de "prolonger ses flancs" pour rejoindre le rempart médiéval, souhait à nouveau exprimé en 1699 dans le Plan d'Auxonne avec une augmentation d'ouvrages proposés. Le bastion reste isolé mais le moineau est conservé pour le lier au corps de place. Un corps de garde est installé.

En 1822 est installée une courtine casematée entre les bastions du Moineau et de Notre-Dame (ou de Khel) avec une poterne (portant la date gravée 1826) de sortie vers le corps de place. Cet ouvrage, ajouté à la seconde courtine bâtie derrière le château, permet au bastion d’être lié à l'enceinte fortifiée de la ville. Au 19e siècle, c'est le dernier bastion "isolé" du corps de place. En 1841, le Génie prévoit la construction d'une demi-lune qui protégerait le côté gauche du bastion, mais, c'est finalement une lunette avancée qui est réalisée

A la fin du 19e siècle, une caserne est installée, occupée de nos jours par les services techniques de la ville.