Most of Downing Park was a farm owned by the Smith family, whose 1750s farmhouse stood at the present location of the pergola.

The idea to build a park was conceived by Mayor O'Dell in the late 1880s. Citing the population growth and increases in property values, he acquired the 25-acre Smith estate, later adding ten more acres.

The City offered the commission to design the park to Calvert Vaux and Frederick Law Olmsted, the designers of New York City's Central Park. The landscape designers agreed in 1889, stipulating that it be named after their mentor (and Vaux's former partner) Alexander Jackson Downing.

Actual construction began in 1894, and the park was opened to the public in 1897.

In addition to the farmhouse, the park originally featured an observatory and a bandshell. The observatory, designed by Calvert's son Downing Vaux, rested on the highest point in the park, commanding spectacular Hudson River views. The structure was torn down in 1961 as part of an "urban renewal" project.

Little is known about the original bandshell, and no clear pictures exist. Described as being built in Downing's 'rustic style,' it was removed in the late 1920s.

At the turn of century, the farmhouse was turned into a smallpox sanatorium. In 1908 the flu epidemic ended; the city condemned the house, and it was burned to the ground. Later that year, architect Frank Estabrook designed the pergola to be built on the farmhouse foundations.

The Shelter House, designed in 1934 by Gordon Marvel, provided shelter in the winter for those ice skating on the Polly Pond.

The outdoor amphitheatre was built in 1946. Used for weekly band concerts for many years, the amphitheatre originally had a moat filled with goldfish at the front of the stage.