La présence humaine est attestée dans le quartier du Marché-Couvert dès le début du 1^er siècle de notre ère. L’homme aménage la rive gauche du bras de la Meuse au pied de l’éperon rocheux, établit des voies de communication dès les IVème-Vème siècles. Le petit rempart fixe le ruisseau Saint-Vanne au Moyen-Âge et des bâtiments religieux sont construits sur cette rive au XIIIème siècle. Un pont, attesté en 1426, permet d’accéder à l’île Saint Nicolas par la Nuefve Porte d’arrière les Augustins.
Les frères de la Pénitence de Jésus Christ s’étaient installés dans la Maison des Sacs (ou sachets) et furent remplacés en 1310 par des frères ermites appelés par l’évêque Nicolas de Neuville, les Augustins. Bénéficiant du droit de besace, ils purent mendier et, sous la conduite de leur prieur conventuel Jocelin, ils achetèrent, sous forme de bail emphytéotique perpétuel, cette ancienne Maison des Sacs, propriété des religieux de Châtillon. Ils disposèrent d’une église ogivale (XIVème siècle), orientée, à une nef et un seul collatéral au nord. Son chevet était éclairé par une grande fenêtre à meneaux. Il y avait également un cloître et des jardins s’étendant jusqu’au bras de la Meuse au sud. Le couvent fut supprimé à la révolution et devint propriété de la Nation le 25 mai 1790.
En 1791, l’évêque constitutionnel Jean-Baptiste Aubry, élu le 20 février 1791 par l’assemblée électorale du département, tenta de conserver l’église mais l’ensemble fut adjugé fin 1794 lors de la vente de biens nationaux pour 90 900 francs, payés en assignats à un spéculateur qui revendit à la découpe. Le 4 juillet 1793, le Conseil Général de la Commune avait décidé de modifier certains noms de rue et c’est ainsi que la rue des Augustins devint la rue de Jemmapes, le Pré l’Evêque devint le Pré de la Fédération.
Les citoyens Dauphin et Sainctelette transformèrent une partie des bâtiments en salle de spectacle qui fut inaugurée le 6 février 1797 pour le carnaval par des bals publics. Le lieu fut très fréquenté de 1803 à 1814 par les prisonniers de guerre britanniques sous le Consulat et l’Empire. Cette salle fut rachetée par la Ville qui en fit son théâtre en 1837. La façade sera refaite et agrémentée d’un péristyle. En 1888, le bâtiment deviendra la bibliothèque municipale jusqu’à la première guerre mondiale.
Dès le 27 décembre 1849, un rapport de la commission des travaux d’utilité générale évoque la nécessité de construire un marché couvert à Verdun. Différents projets sont étudiés, on pense à la place de la Madeleine (place de la libération), à l’emplacement de la halle au blé (théâtre actuel), au quai de la boucherie (quai Leclerc), en aval du Moulin du Puty (place de la Nation, mess des officiers), à la Place Sainte-Croix (place Chevert) voire même sur la Meuse, et un projet sur le quai des Augustins de l’architecte de la ville, Monsieur Cauyette. On y ajoute un projet de percement d’une rue entre les rues Mazel et des Augustins.

La construction est décidée suite aux délibérations des 21 juin 1851 et 9 avril 1852 "sur l’emplacement des anciens Augustins conformément aux plans et devis de l’architecte de la ville". On précise que la "dépense est évaluée à près de 300 000 francs et il y aurait lieu de recourir à un emprunt de 286 000 francs sur 19 ans½". On ajoute qu’il faut tenir compte de "l’expropriation des maisons qui couvrent le terrain destiné au marché couvert ".
On examine sous la présidence de Monsieur Cartier, Maire, les propositions des entreprises lors du Conseil Municipal du 9 février 1853.
Les travaux de démolition et de construction sont menés bon train puisque le compte administratif pour 1854 nous indique concernant les travaux du Marché-Couvert : "Les deux rues de service (cour Clouet) ont été pavées, avec trottoirs" et " la pose des grilles destinées à fermer les rues de service "faite". Tel qu’il se présente aujourd’hui , avec son corps principal et ses accessoires, le Marché-Couvert semble répondre aux intentions du Conseil et convenir à sa destination. Il aura été mené à complète fin en vingt mois".
Le Conseil Municipal votera une gratification de 1 200 francs à Monsieur Cauyette, l’architecte.
On avait songé à élaborer un règlement, on s’était renseigné à Nancy et à Metz et dans sa séance du 30 août 1853 on propose la perception de droits de place pour les foires ou marchés ainsi que dans les rues adjacentes ou de services en prévision du budget de 1854.
On envisageait la mise en place de 36 boutiques et de 16 emplacements. 18 boutiques de bouchers, 9 de charcutiers louées 170 francs par an, 9 de marchands divers à 125 francs minimum, les emplacements pour le fromage, les volailles et les fruits à 75 francs. 44 places seraient réservées aux jardiniers et aux maraîchers à 22 francs.
Les tarifs étaient différents selon les animaux. Pour les voitures on tenait compte du nombre de roues, de chevaux attelés et un cheval dételé et mis derrière la voiture devait payer 15 centimes. Ces tarifs sont adoptés lors de la séance extraordinaire du 18 octobre 1853 et sont " exécutoires à dater du 1^er janvier 1854 ".
Dans son compte moral et administratif pour l’exercice 1854, le Maire constate une baisse des produits attendus l’expliquant par " le manque de fruits, la détresse générale et le choléra ".
Il y eut des divergences entre les propriétaires des maisons sur la "voie de communication qui doit relier la place Mazel (place Foch) au Marché - Couvert" et "l’appréciation du jury d’expropriation".
La liaison entre les rues de Rû et Mazel ne fut achevée qu’en 1867.