Le Vieux-Marché-aux-Poissons longe l’ancien mur d’enceinte de la Ville, détruit en 1248, dont il subsiste l’étroit fossé dit Ulmergraben qu’on peut notamment voir rue du Vieil-Hôpital. Sa dénomination provient des étaux de poissonniers qui se trouvaient au débouché de la place Saint-Martin (ou Marché aux herbes, actuelle place Gutenberg).
Elle a d’abord porté le nom des savetiers (Under Altbüssern), des marchands de bestiaux (Under Fuoteren, en latin inter pabulatores) ou des bouchers (Under Metzigeren) avant que le nom des poissonniers supplante les autres (Vischmercket). Elle a longtemps fait partie de la voie principale qui traversait la Ville pour se rendre de Saverne en Allemagne.

Sur le plan Blondel (1765), la rue forme séparation entre les cantons VII à l’ouest et VI à l’est.