Erste Entdeckungsreisen in das Gebiet des heutigen New York fanden schon 1524 durch Giovanni da Verrazano und 1609 durch Henry Hudson statt. Ab 1610 begannen niederländische Kaufleute einen lukrativen Fellhandel mit den dort lebenden Indianern. Am 27. März 1614 erhielt die neu gegründete Compagnie van Nieuwnederlant (Neuniederland-Kompanie) von den Generalstaaten ein Monopol für den Handel in dem Gebiet.
Im Oktober 1618, zehn Monate nach Ablauf des Handelsmonopols, bewarb sich die Kompanie um eine neue Charter. Zu diesem Zeitpunkt wurde von den Generalstaaten aber bereits die Gründung einer neuen Kompanie, der Niederländischen Westindien-Kompanie (WIC) erwogen. Am 3. Juni 1621 erhielt die WIC von der Republik der Sieben Vereinigten Niederlande einen Freibrief für den alleinigen Handel in Amerika. Die Kolonisation begann 1624, als sich 30 niederländische Familien auf der Insel Manhattan und in der Gegend des Delaware ansiedelten.
1626 kaufte Peter Minuit den Eingeborenen, wahrscheinlich ein Zweig der Lenni-Lenape-Indianer, die die Insel „Manna-hatta“ nannten, das Eiland für 60 Gulden ab. Die neu gegründete Siedlung erhielt den Namen Nieuw Amsterdam und wurde zur Hauptstadt der Kolonie Nieuw Nederland. In der Siedlung herrschten bald chaotische Verhältnisse. Unter der Herrschaft von korrupten Gouverneuren nahm die Kriminalität enorm zu.
1647 entschloss sich die Niederländische Westindien-Kompanie wieder für Ordnung zu sorgen. Diese Aufgabe sollte Petrus Stuyvesant übernehmen. Während seiner 17-jährigen Amtszeit als Gouverneur wurden das erste Krankenhaus, das erste Gefängnis und die erste Schule gebaut. Als Schutz vor Überfällen ließ er 1652 im Süden der Stadt quer über die Insel einen Wall aufschütten, der später der dort verlaufenden Straße ihren Namen gab, der Wall Street. Am 2. Februar 1653 erhielt Nieuw Amsterdam die Stadtrechte.
Im Verlauf des Zweiten Englisch-Niederländischen Seekriegs ergab sich die Stadt am 27. August 1664 kampflos einer von Richard Nicolls geführten Flotte. Zuvor hatte König Charles II. seinem Bruder James, Herzog von York, dem späteren König Jakob II., die nordamerikanische Küste zwischen Neuengland und Maryland zugesprochen; die Kolonie wie die Stadt wurden zu Ehren des Herzogs in New York umbenannt. 1667 gaben die Niederländer alle Ansprüche auf die Kolonie im Frieden von Breda auf, in dem ihnen dafür die Rechte an Suriname zugesichert wurden. Im folgenden Dritten Englisch-Niederländischen Krieg nahmen die Niederländer 1673 die Kolonie kurzzeitig wieder ein, bevor sie das Land endgültig durch die Unterzeichnung des Vertrags von Westminster am 19. Februar 1674 abgeben mussten.