A l'emplaçament del parc, al Fort Tryon s'hi va desenvolupar una de les batalles de la Guerra d'independència. El 16 de novembre del 1776, 600 partidaris americans van intentar oposar-se a 4.000 mercenaris germànics vinguts de l'Estat Popular de Hesse, a sou de la Gran Bretanya. Margaret Corbin, ferida durant l'enfrontament, va ser la primera dona a portar armes durant aquest conflicte. Els britànics es van endur la victòria, i el fort va ser rebatejat en honor de sirWilliam Tryon, darrer governador britànic de la colònia de Nova York.
El parc va esdevenir, ulteriorment, propietat de diversos homes rics americans, com el Dr. Samuel Watkins, fundador de Watkins Glen, el general Daniel Butterfield, Boss Tweed i C. K. G. Billings. John Davison Rockefeller Junior va comprar la finca a Billings el 1917. Va encarregar a Frederick Law Olmsted, Jr, el fill del dissenyador de Central Park, de condicionar un parc amb l'objectiu d'oferir-lo a la municipalitat de Nova York. Els treballs es van desenvolupar durant la Gran depressió i van oferir nombrosos llocs de treball. El projecte incloïa sobretot la construcció de l'estació de metro del carrer 190 a l'IND Eighth Avenue Line. La realització del parc es va acabar el 1935. S'hi troben nombroses plantacions, sobretot un jardí de brucs.
Als anys 1970, havent abandonat el manteniment del parc la municipalitat (New York City Department of Parks and Recreation), va esdevenir un refugi per als sense sostre, les prostitutes i els revenedors de droga. El 1995, sota l'impuls de Bette Midler, l'associació Nova York Restoration Project n'ha pres el control i l'ha renovat completament.
Una part de la pel·lícula de Clint Eastwood, Un xèrif a Nova York (Coogan's Bluff) ha estat rodada a Fort Tryon (i en destaca l'escena final).
