Die mittelalterlichen Strassen waren anfänglich wohl nur mit einer Kieskofferung befestigt. An Gefällen verhinderten vermutlich quer über den Weg gelegte Holzbalken ein Ausschwemmen, wie die Bezeichnung "an den Swellen" für den Bereich um die obere Freie Strasse nahe legt. Eine erste Pflasterung unbekannten Umfangs ist für das Jahr 1387 belegt. Der planmässige Steinbelag der Strassen wurde zu Beginn des 15. Jahrhunderts in Angriff genommen. Seit 1417 sind das Amt eines "Besetzermeisters" sowie die Ausgaben und Einnahmen (durch Einwohnerbeiträge) für das "Besetzwerk" aktenkundig. Aeneas Silvius Piccolomini lobte in seinen beiden Beschreibungen Basels 1433/34 und 1438 die saubere und dauerhafte, wenn auch für die Füsse beschwerliche Befestigung mit unbearbeiteten Rheinkieseln, die mit runder Oberfläche aufrecht stehend in Sand gebettet wurden. Die etwas jüngere Methode der Pflasterung mit halbierten Kieseln, die mit der glatten Seite nach oben in Reihen versetzt wurden, blieb bis ins 19. Jahrhundert vorherrschend und hat sich beispielsweise auf dem Münsterplatz und am Schlüsselberg sichtbar erhalten.

Seit dem zweiten Drittel des 19. Jahrhunderts führte der durch zunehmenden Verkehr motivierte Stadtumbau zur Umpflasterung fast sämtlicher Strassen und zur Schaffung von Trottoirs. Für diese erprobte man schon 1840 in der Eisengasse den Asphaltbelag, der schliesslich allgemein gebräuchlich wurde. Mit dem Anschluss an das Eisenbahnnetz 1844 setzte sich die Pflasterung mit rechteckigen Bruchsteinen durch, die zunächst vorwiegend aus den Quarzsandsteinbrüchen von Voegtlinshofen im Elsass bezogen wurden. Dieses Material findet sich heute noch im mittleren Abschnitt des Rheinsprungs, im Martinsgässlein und auf dem Platz vor der Westfassade der Martinskirche. Später wurden auch Grosspflaster aus Grauwacke und Granit verwendet.

In stark frequentierten Bereichen drängten die Anwohner am Ende des 19. Jahrhunderts auf die Benutzung von Geräusche dämmendem Holzpflaster. Ebenfalls durch die Lärmbelastung motiviert waren um 1880 Versuche mit Makadam-Fahrbahnen zum Beispiel auf dem Münsterplatz. Seit 1900 wurden vermehrt Kleinpflastersteine, teilweise in bogenförmiger oder dekorativer Anordnung, gebraucht. Kleinpflaster aus Alpnacher Quarzsandstein, der seit 1904 gebrochen wurde, liegt heute noch im Pfluggässlein, in der Weissen Gasse und im Ringgässlein. Nach 1960 wurden viele Pflasterstrecken überteert oder gänzlich aufgehoben. Mit der Verkehrsberuhigung der Innenstadt und der Schaffung von Fussgängerzonen kehrt seit Mitte der 1970er-Jahre jedoch der Steinbelag zurück.