1836 überließ Peter Gerard Stuyvesant (1778–1847), der Ururenkel von Petrus Stuyvesant (heute allgemein als Peter Stuyvesant bezeichnet), mit seiner Ehefrau Helen Rutherford eine Fläche von knapp 1,6 Hektar der Stuyvesant Farm für symbolische fünf US-Dollar der Stadt New York für einen öffentlichen Park, der ursprünglich Holland Square heißen sollte.
Eine Klage von Stuyvesant im Jahre 1839 trieb das Bauvorhaben des öffentlichen Parks voran, der gemeinsam mit St. John’s Square (nicht mehr existent), dem kurz zuvor geschaffenen Washington Square Park und dem privaten Gramercy Park als Grünanlage in einem Gebiet fungieren sollte, von dem man annahm, dass hier ein gehobenes Viertel entstehen würde. Doch erst 1847 begann die Stadt damit den Park anzulegen, indem sie einen prächtigen gusseisernen Zaun errichten ließ, der heute noch steht und der zweitälteste gusseiserne Zaun New York Citys ist. 1850 schlossen zwei Brunnen die Gestaltung des Parks ab und der Park konnte formell der Öffentlichkeit übergeben werden.
Das erste Haus in diesem Viertel wurde 1842–1843 errichtet. 1858 zog das Krankenhaus „New York Infirmary for Women and Children“ (heute: New York Downtown Hospital), das von Elizabeth Blackwell gegründet wurde und sich vorher in der 7th Street in der Nähe des heutigen Tompkins Square Park befand, an den Stuyvesant Square (321 East 15th Street). Heute befinden sich Wohnungen in diesem Gebäude, nachdem das Krankenhaus erneut umziehen musste. Bis Ende des 19. Jahrhunderts behielt Stuyvesant Square sein elegantes Prestige, vor allem wegen der Ärzte, die in den Krankenhäusern arbeiteten, die Stuyvesant Square säumten.
Wie viele andere städtische Parks wurde auch der Stuyvesant Square seither umfassenden Sanierungsarbeiten unterzogen. In den 1930er Jahren wurde der Park vom Landschaftsarchitekten von Parks CommissionerRobert Moses – Gilmore D. Clarke – verändert, indem Toiletten, Spielplätze und andere Annehmlichkeiten hinzugefügt wurden. Der Park wurde 1937 wiedereröffnet. In den 1980er Jahren wurden die beiden Brunnenanlagen und der gusseiserne Zaun saniert. Darüber hinaus wurde das Kopfsteinpflaster aus Blaustein in zwei Ellipsen neu verlegt. Dabei wurden zugleich die Rasenflächen, Blumenbeete und Sträucher erneuert. Einige alte Bäume, englische Ulmen und Steinlinden, gedeihen weiterhin gut.
Weitere Bereicherungen des Parks sind die Skulptur von Petrus Stuyvesant von Gertrude Vanderbilt Whitney (1941) und die Statue von Antonín Dvořák von Ivan Meštrović aus dem Jahre 1963, die 1997 in den Park versetzt wurde.
Der Park und seine unmittelbare Umgebung wurden 1975 zum Historic District erklärt und damit unter Denkmalschutz gestellt.