Pas als het verleden wordt opgeschreven, beginnen we van geschiedenis te spreken. De periode vóór die tijd noemen we voorgeschiedenis of prehistorie. De geschiedenis van Haarlem begint met enkele vermeldingen in oude documenten. Zoals in de lijst van de Utrechtse Sint Maartenskerk over bezittingen in Haarlem, die uit de vroege 10e eeuw dateert (tussen 918 en 938). Latere vermeldingen komen uit de oorkonden van het klooster te Windesheim (10de, 11de eeuw), waarin een Mariakerk te Haarlem wordt genoemd. Dat houten kerkje behoorde tot de parochie van Velsen en is in de 14de eeuw bijna helemaal afgebrand. Het stond op de plaats waar nu de Grote of Sint-Bavokerk staat.
In die tijd werd nog maar heel weinig opgeschreven. Rond 1400 was één enkele stevige kist voldoende om alle oorkonden van de stad Haarlem in te bewaren. Die kist is nog steeds te zien. Hij bevindt zich in de Grote Kerk. Het belangrijkste stuk was een oorkonde uit 1245 waarin beschreven stond dat Haarlem van Willem II, graaf van Holland en Zeeland, stadsrecht kreeg. Als het niet in plechtige woorden was opgeschreven, hadden we dat nu niet meer geweten. Het was een belangrijke gebeurtenis. Het betekende dat hier eigen Haarlemse regels en eigen Haarlems recht van kracht waren. Het betekende ook een belangrijke stap voor de inwoners, want ‘stadslucht maakt vrij’. Dat was in die tijd een heel moderne gedachte. Het betekende dat een stadsburger niet langer onderhorig was aan de willekeur van een landheer; hij hoefde bijvoorbeeld niet langer gratis een aantal dagen per jaar herendiensten te verrichten. Hij was vrij om een vak te leren bij een gilde en zelfstandig vakman te worden, of zijn werkkracht aan te bieden aan wie daarvoor loon wilde betalen. Een gilde, een vereniging van vakbroeders, maakte zelfstandig afspraken over de prijs en de kwaliteit van producten of diensten; vaak ook over uitkeringen bij ziekte, werkloosheid of overlijden.
De stad mocht mensen van buiten tot stadsburger (poorter) benoemen, of misdadigers uit de stad verbannen. Dat was een zware straf – daardoor verloor een poorter meteen al zijn rechten weer. Het stadsbestuur mocht zelf belastingen heffen en een eigen stadsleger oprichten, zelf rechtspreken en zelf straffen. En dat alles stond op perkament, met grote zegels eraan dat het geschrevene rechtsgeldig was! Haarlem werd na 1245 als de tweede stad van Holland beschouwd, het werd eeuwenlang direct na Dordrecht genoemd. Haarlem was in dat laatste deel van de Middeleeuwen een belangrijke stad geworden.