A en croire les vieilles chroniques, c'est Pépin le Bref, fils de Charles Martel, qui a fait ajouter un choeur en pierre à l'antique église de Clovis. Charlemagne acheva l'œuvre commencée par son père et dota la basilique d'une quantité de reliques précieuses. Sous Louis le Débonnaire, la cathédrale surpassait en magnificence toutes les églises édifiées le long du Rhin.
L'empereur Henri II, d'Allemagne, vint à Strasbourg et passa le temps de son séjour à assister à la célébration du culte dans la cathédrale. La légende dit qu'il manifesta l'intention de renoncer à la couronne impériale et de finir ses jours dans
la confrérie des prêtres voués au culte de la Vierge. Ce qui paraît plus certain, c'est qu'il dota la cathédrale d'une riche prébende. Le prélat qui en jouissait occupait la place du fondateur et s'appelait le roi du choeur.
Le jour de Saint-Jean-Baptiste de l'année 1007, la foudre tomba sur la cathédrale et sur l'église Saint-Thomas. Les deux édifices furent réduits en cendres. L'évêque Werner résolut de les reconstruire. Il promit la rémission de leurs péchés à tous ceux qui y donneraient leur concours moyennant argent ou travail. Une collecte fut organisée dans le pays et comme elle produisit des sommes considérables, on fit appel aux architectes les plus renommés pour ériger un monument merveilleux.
La construction fut commencée en 1015. On enleva les fondations de l'église de Clovis; on creusa à une grande profondeur et, ayant atteint les nappes d'eau souterraines, on y enfonça d'énormes pieux au moyen d'un marteau-pilon formidable qui, pendant longues années, fut conservé au dépôt municipal des charpentes (Zimmer-Werkhof). Les blocs de pierre de taille furent extraits des carrières de la vallée de la Couronne (Kronthal), près Wasselonne, et d'immenses charrois les amenaient à Strasbourg. Toute la population des environs participait à ces corvées. Chacun voulait gagner le salut de son âme en contribuant à édifier le monument consacré à la Mère de Dieu. Sur la place près de la cathédrale, du côté sud, on avait élevé de grandes baraques, où l'on donnait à boire et à manger aux voituriers qui amenaient les matériaux de construction, et c'est à cette circonstance que la place a dû le nom de « Cour des corvées» (Frohnhof), nom qu'elle a gardé pendant des siècles.
La légende rapporte que le premier qui amena un chargement de pierre, était un meunier. Vêtu d'une casaque rouge, les cheveux crépus, petit de taille, il était monté sur un grand cheval blanc trainant une voiture chargée d'un bloc énorme. Il fut accueilli par les acclamations de la foule, et pour perpétuer le souvenir de son action, l'un des tailleurs de pierre sculpta la statue équestre du meunier et la plaça contre l'un des piliers de la cathédrale. Le fait est attesté par Grandidier, dans son histoire de l'église de Strasbourg, où il parle « du petit homme à cheval, taillé dans la pierre, au chapiteau du grand pilier, vis-à-vis la loge du garde, qu'on prétend représenter le meunier qui a amené la première pierre de cet édifice ».
