Antes de la llegada de los europeos, el extremo norte de Manhattan formaba parte del territorio de los lenapes, que cultivaban, pescaban y seguían los ríos según las estaciones. En 1658 el gobernador neerlandés Peter Stuyvesant fundó aquí una aldea, Nieuw Haarlem, nombrada por la ciudad neerlandesa de Haarlem.
El nombre sobrevivió a todos los cambios de bandera: neerlandesa, inglesa y, después, estadounidense. Muchos detalles de esta época están poco documentados, así que conviene contrastar los relatos populares con museos y archivos.