In 1609, during one of the many voyages the Dutch financed in search of the Northwest Passage, Henry Hudson sailed the Hudson River, docking his ship in Haverstraw Bay. It was here that the Dutch declared the Hudson River as property of the Dutch.

Haverstraw was founded in 1666, but the village, known as Florus Falls and also as Waynesburgh, wasn't legally established until 1854 as the Village of Warren. Under an Act of the State Legislature, the name of the village was changed to "Haverstraw" on April 14^th, 1874.

The village is one of the first to appear on maps of North America, listed as "Haverstroo", which means oat straw.

Strategically located on the Hudson River, the village was home to a number of skirmishes between the British Army and the Continental Army of the Americans during the American Revolutionary War.

Haverstraw was the site of the most grevious treason of the early years of the United States. During the night of September 19 and September 20, 1780, the English Emissary, Major John André, was rowed from the sloop-of-war Vulture to a beach below the Long Cove on the southern boundary of Haverstraw. The negotiations to sell the plans to West Point were not completed by dawn, and Benedict Arnold and André traveled to the Belmont House, owned by Thomas Smith and occupied by his brother Joshua Hett Smith, on the grounds of what is now Helen Hayes Hospital in West Haverstraw, New York. The house has since been known as the Treason House.

Commonly referred to as "Bricktown", Haverstraw was famous for its brickmaking, which was a major industry for the village. Brickmaking was so popular due to the clay formed by the Hudson River's water and the rich soil that lined Haverstraw's waterfront, that it was nicknamed the "Brickmaking Capital of the World". Many of the old brownstone and brick structures that were constructed in New York City in the late 1890s-early 1900s were composed of bricks manufactured by Haverstraw. At one point, in the early 20th century, there were more than 40 brickmaking factories lining the Hudson River within the village. Although brickmaking involved all the ethnic groups, 60 percent of the brickyard workers were African-Americans.

On the night of January 8, 1906, a landslide demolished a large residential portion of the village. Firefighters responded immediately but faced enormous odds because of burst valves and water mains, gas explosions and hoses which periodically froze because of the cold night. The landslide, a pit about 150 feet deep, claimed five Haverstraw streets from Allison to Jefferson Roads, 21 buildings and the lives of 4 firefighters and 17 residents. Despite the events, the village rebounded. Eight years later, however, the Cleary-Newman murder case took place. The village announced in 2007, the 101 anniversary of the landslide, that a memorial would be erected in honor of the victims of the landslide.

The brick industry continued to thrive until World War II, in which brick began to lose its value significantly. Shortly after, the village's main industry of brickmaking declined and left the village. The economic vitality of the village greatly decreased. Because of the amount of vacancies and the relatively inexpensive housing available, the village opened up to Hispanic migration, and the village has since become home to many Hispanic immigrant families since the 1950s. Many families of Hispanic descent take part in the village's festivals that take place annually. The Puerto Rican Day Parade and Festival take place in the village's downtown in early June, the Dominican Day Parade and Festival occur in late August and in September, the multi-cultural festival is assembled.

September 2004 marked the village's 150th anniversary, celebrated by a festival along the village's waterfront. The future of this river village gleams bright with a large revitalization project that revitalizes the downtown business district and develops its waterfront with a large residential project.

As a cost-saving measure, at midnight on January 1, 2006, the Village of Haverstraw Police Department was merged with the Town of Haverstraw Police Department.

In July 1920, New York Yankee outfielder Babe Ruth spent time in Haverstraw, to film a movie - Heading' Home. A local baseball field bears the Hall of Famer's name due to his visit.