Selon le chanoine Quentin de La Fons qui écrit vers le milieu du 17e siècle, la nef de la collégiale fut pavée en 1495, à l'issue de la reconstruction du monument. A cette occasion, les dalles funéraires qui se trouvaient dans la nef furent retirées puis replacées dans les collatéraux du choeur, libérant l'espace, et un labyrinthe octogonal fut mis en place vers l'entrée de la nef. De nombreuses interprétations iconographiques ou symboliques ont été avancées concernant ces labyrinthes circulaires ou octogonaux qui ornent de nombreuses cathédrales ou églises françaises et européennes. La plus probable consiste à voir dans son parcours un exercice pénitentiel, un substitut du voyage en Terre Sainte pour les fidèles qui ne pouvaient s'y rendre, ou encore l'accomplissement d'un "chemin de croix", la longueur des méandres étant censée correspondre à la longueur du chemin parcouru par le Christ entre la maison de Pilate et le Calvaire. La date tardive d'exécution du labyrinthe de la collégiale de Saint-Quentin en fait l'un des derniers à avoir été mis en place, ce type de décor symbolique disparaissant au cours du 16e siècle et étant remplacé par le chemin de croix. Le labyrinthe de la collégiale de Saint-Quentin est identique à celui de la cathédrale d'Amiens, à l'exception du décor de l'octogone central, aujourd'hui parfaitement lisse à Saint-Quentin. Toutefois, dans sa description longue et précise de la collégiale en 1855, le baron Ferdinand de Guilhermy semble y deviner les traces d'un décor gravé ou rapporté, accroissant ainsi la ressemblance entre les deux labyrinthes. Depuis sa création, le labyrinthe de Saint-Quentin a bénéficié de plusieurs restaurations, en particulier après l'incendie des combles de l'église en 1669, qui avait provoqué la destruction de l'orgue et la chute de pièces de charpente enflammées à cet emplacement du dallage. Fortement endommagé pendant la Première Guerre mondiale, le labyrinthe a été restauré pour la dernière fois au cours de la longue réhabilitation de l'édifice, qui a suivi le conflit.