Харлем је било седиште грофова Холандије у средњем веку.
Витезови из Харлема су се 1219. упутили у Пети крсташки рат под вођством грофа Виљема I. Одатле потиче крст на градском грбу и застави. Витезови из Харлема су исте године заузели град Дамијету у Египту.
Гроф Виљем II је дао градске привилегије Харлему 1245.
У позном средњем веку Харлем је био познат по изради текстила, бродоградњи и производњи пива. Био је тада други по величини град Холандије (после Дордрехта).
Град је био под шпанском опсадом у 16. веку када је становништво тешко пострадало. Војвода Фернандо од Толеда је заузео градску тврђаву 1573. Тада је избио пожар у коме је изгорела трећина града. Шпанци су напустили Харлем 1577, а протестанти и католици су добили једнака права. Због тога, град је постао привлачан за многе избеглице из Француске и Фландрије које су знатно допринеле привредном успону. Постоје подаци да је 1621. више од половине становништва било родом из Фландрије.
