Cette rue, presque entièrement bâtie en 1250, portait le nom de Gravelier. Un rôle de taxe de 1312 indique une maison appartenant à un nommé Gravelier, boucher. Il est possible qu'un des ancêtres de ce marchand ait donné son nom à cette voie publique, qu'on appelle aujourd'hui par altération rue des Gravilliers. 

Quoiqu'il en soit, elle s'étendait anciennement, comme de nouveau aujourd'hui, jusqu'à la rue Saint-Martin.  Mais  à la fin du XVIl^e siècle et pendant deux siècle, le nom de Jean-Robert fut assigné à la partie de cette voie publique comprise entre les rues Transnonnain  (tronçon de l'actuelle rue Beaubourg entre la rue Michel-Le-Comte et la rue au Maire) et Saint-Martin et Turbigo. 

Le passage des Gravilliers qui donne accès à la rue Chapon s'ouvre au n°19. Au n° 24. était autrefois la Cour de Rome; elle existait en 1382 sous le nom de rue aux Cordiers, puis cul-de-sac du Puits-de-Rome (en partie). La cour avait une issue 9, rue des Vertus, et une autre 7, rue au Maire. Deux autres passages ont également existé dans cette rue : au n°26 (passage Alombert) et au n°34 (passage Barrois).

Une décision ministérielle du 23 frimaire an VIII, signée Laplace, fixa la largeur de la rue des Gravilliers à 10 m. Cette dimension a été ensuite portée à 12 m.