Niemand weet precies waar de naam Haarlem vandaan komt, de oudste sporen gaan terug tot ver voor het begin van onze jaartelling. Een groot deel van westelijk Nederland ligt onder de zeespiegel. Maar Haarlem ligt voor een groot deel op een zandplaat die ca. 5000 jaar geleden door de zeestroming is gevormd; dat zijn de oudste strandwallen.
Die zandplaat, omringd door zompige moerasgebieden en veel water, was een hoge en veilige doorgangsroute. Het was lange tijd de enige verbindingsweg tussen het noorden en het zuiden van Holland. In de Romeinse tijd liep hier waarschijnlijk een oude heirweg (= legerweg), vermoedelijk naar Velsen, waar een Romeins fort lag, en naar Castricum. Haarlem was een nederzetting aan die weg door de duinen, dicht bij de rivier het Spaarne.
Deze oude duinweg loopt als Herenweg vanuit Zuid-Holland naar Haarlem, wordt daar achtereenvolgens Wagenweg, Houtplein, Grote Houtstraat, Gierstraat, Koningstraat, kruist de Grote Markt, gaat verder als Barteljorisstraat en Kruisstraat, en vervolgt buiten de stad als Herenweg zijn loop, tot aan Egmond. Een tweede duinweg, meer westelijk, liep over het huidige Aerdenhout en Bloemendaal, en kwam in de omgeving van Velsen samen met die meer oostelijk gelegen route. Na de vestiging van de nederzetting liepen er ook verbindingen van oost naar west, al was het maar om verse vis aan het achterland te verhandelen.
De oudste bewoningssporen gaan terug tot voor het begin van onze jaartelling. Uit die oudste tijden is weinig bekend; wat we ervan weten is opgemaakt uit bodemvondsten die wijzen op landbouw- en veeteeltactiviteiten. Uit de Romeinse tijd zijn in Haarlem geen duidelijke sporen te vinden. De oudste schriftelijke vermelding van onze stad dateert van ergens tussen 918 en 938. Dat wil zeggen dat er lang voordien al een woonkern moet zijn geweest.
De naam Haarlem is veel ouder dan de eerste schriftelijke vermelding. De betekenis van de naam is in de loop der eeuwen verloren gegaan. Dat komt omdat in het vroeg- en Middelnederlands het woord ’haar’ zoveel verschillende betekenissen kon hebben, en de toevoeging ’lem’ daardoor niet goed meer te duiden is. Misschien is het een verbastering van Haarlooheim (’haar’ in de betekenis van: hoge zandgrond, ’loo’ = bos, ’heim’ = huis, nederzetting). De naam werd op verschillende manieren geschreven. Haerlem of Hairlem. Of deftig verlatijnst tot Harlemum. In de 10e eeuw is er een houten Mariakerk op de Grote Markt, en een grote stenen woning van de graaf van Holland. Om dit centrum heen breidt de nederzetting zich uit.