La porte Notre-Dame anciennement porte du Bali fait partie des cinq portes qui au 14e siècle donnent accès à l'intra-muros.
A cette date, les portes de la ville ne disposent pas de tours. Le passage, tel celui de la porte Saint-Salomon et probablement celle du Bali se fait entre deux guérites aménagées dans l'épaisseur de la courtine.
Comme d'autres entrées de la ville, la porte Notre-Dame est renforcée à la fin du 16e siècle par un bastion de terre aménagé et doté d'un pont-levis. Cet ouvrage est reconstruit en pierre au début du 17e siècle (1616-1618) par l'architecte Jean Bugeau. sans doute est-il doté à cette époque d'une ruelle en son milieu et d'une seconde porte qui ouvre sur la place du Marché comme on peut le voir sur les anciens plans du 18e siècle.
La porte Notre-Dame est démolie en 1784 d'après Thomas-Lacroix. En 1870, les murs attenant à cette porte font l'objet de travaux. Les archives départementales conservent un plan dressé en 1870 à cet effet. La moitié nord du bastion Notre-Dame dit de l'évêché a disparu lors de la construction à cet emplacement d'un important immeuble de rapport quand est prise la décision de détruire l'ancien palais épiscopal à partir de 1867.