While visiting his sweetheart and future wife, Sarah Teed, he was captured by Tories led by his future brother-in-law and imprisoned in the notorious "Sugar House " prison in New York City in 1780. Escaping the prison by jumping from a window, he went to the livery stable of a friend and obtained a German military Jäger or Hessian coat, green with red trim, which aided in his escape. As part of an armed patrol with fellow militiamen David Williams, and Isaac Van Wart, Paulding seized Major John André, who had left Benedict Arnold after discussing the defection and betrayal of Arnold. The site is now called Patriot's Park in Tarrytown, NY. Andre, seeing the Hessian coat Paulding was wearing, may have assumed him to be a member of the "cowboys," or pro-British marauders who raided the Neutral Ground for cattle and supplies. Searching him for valuables, they discovered documents of André's secret communication with Benedict Arnold. The militiamen, all local farmers of modest means, refused his considerable bribe and instead delivered him to the Continental Army. Arnold's plans to surrender West Point to the British were revealed and foiled, and André was hanged as a spy.
With George Washington's personal recommendation, the United States Congress awarded Paulding, Williams, and Van Wart the first military decoration of the United States, the silver medal known as the Fidelity Medallion. Each of the three also received federal pensions of $200 a year, and prestigious farms awarded by New York State.
The celebrated trio became only more celebrated after the war: commemorations large and small abound in Westchester County (see below), and elsewhere throughout the original colonies. By an Act of Congress, the new state of Ohio (1803) included the counties of Paulding, Van Wert (anglicised spelling), and Williams. Paulding himself was held in particularly high regard by early American historians, as the standard 19th-century retellings of the event give prominence to Paulding, crediting him with the decision-making and initiative at the scene. Consequently, several villages and counties, in addition to Paulding County, Ohio along with its county seat, Paulding, are named in his honor: Paulding County, Georgia; Paulding, Michigan (site of the mysterious Paulding Light); Paulding, New Jersey; Paulding, Mississippi and Paulding, Missouri. Additionally, the villages of Tarrytown (where there is also a John Paulding Elementary School), Cold Spring and Elmsford, along with the cities of Peekskill and White Plains, in New York, each have a street named for Paulding (as well as ones for Williams and Van Wart). The Fire Department of Sparkill, New York, maintains the John Paulding Engine Co., founded in 1901.
Though hailed as national heroes, Paulding and the others did see their reputations impugned by some. André at his trial had insisted the men were mere brigands; sympathy for him remained in some more aristocratic American quarters (and grew to legend in England, where he was buried in Westminster Abbey). Giving voice to this sympathy, Representative Benjamin Tallmadge of Connecticut, who had been present as an American officer in Westchester County in 1780 and had a low opinion of the three men and in general accepted Andre's account of the capture and search, persuaded Congress not to grant the men a requested pension increase in 1817, publicly assailing their credibility and motivations. Despite the slight, the men's popular acclaim continued to grow throughout the 19th century, although opinion on their motives and actions remained divided. Some modern scholars have interpreted the episode as a major event in early American cultural development, representing the apotheosis of the common man in the new democratic society.
John Paulding was a self-sufficient farmer: a strong, sturdy man, he stood over six feet tall, unusual for the era. He married three times in his life, and was the father of nineteen children. He died in 1818 at Staatsburg, Dutchess County, New York of natural causes. His last words were reported to be: "I die a true republican." He is buried in the cemetery of Old Saint Peter's Church in Van Cortlandtville, Cortlandt Manor, NY. The grave is marked by a large marble monument with the epitaph: "FIDELITY - On the morning of the 23rd of September 1780, accompanied by two young farmers of the county of West Chester, he intercepted the British spy, André. Poor himself, he disdained to acquire wealth by the sacrifice of his country. Rejecting the temptation of great rewards, he conveyed his prisoner to the American camp and, by this noble act of self-denial, the treason of Arnold was detected; the designs of the enemy baffled; West Point and the American Army saved; and these United States, now by the grace of God Free and Independent, rescued from most imminent peril."
Paulding's descendants are numerous but perhaps the best-known of them is his son Hiram Paulding (b.1797 - d.1878), who served in the War of 1812 and fought in the Battle of Lake Champlain; he rose to become a Rear Admiral in the United States Navy and retired only after the end of the American Civil War.
In 1853, a monument was erected at the site of André's capture in Tarrytown. On the event's centenary in 1880, it was topped with the statue of a minuteman. Carved by the sculptor William Rudolf O'Donovan (1844–1920), the statue is reputedly in the likeness of Paulding himself. It is located in Patriot's Park, which was added to the National Register of Historic Places in 1982. A street called Paulding Drive in Chappaqua, New York was named in his honor.
- Cray, pp. 371-397
- Raymond, pp. 11-17
-  Reynolds, Cuyler "Genealogical and family history of southern New York and the Hudson River Valley" Volume III, Lewis Historical Publishing Company, New York, 1914, page 1281-1282. Retrieved July 25, 2011
- “The crisis of the revolution” By Abbatt, William; Hart, John; Campbell, Charles A., Sons of the American Revolution, New York State Society, 1899. page 29. Retrieved July 25, 2011
-  Ward, Harry M., "The war for independence and the transformation of American society," Routledge, 1999, page 67. ISBN 1-85728-656-1. Retrieved July 25, 2011
- Builders, p. 49
- "The new American cyclopedia" Appleton, New York, 1857. Vol. 1, "André," page 549551. "In regard to the captors of Maj. André, suspicions that they were not governed altogether by honest motives, have to some extent gained ground in recent years." "It is not the least interesting feature of the story of André, the fascination of which only seems to increase with time, that 40 years after his death, the suspicion which we have noticed should arrest public attention, and be likely henceforth always to divide it." Retrieved July 25, 2011
- "JOHN PAULDING MEDAL FOUND.; Was Presented to Him by Congress for Major Andre's Capture." New York Times. May 10, 1896.
- John Paulding at Find A Grave
- Bolton, p. 75
- Staff (2009-03-13). "National Register Information System". National Register of Historic Places. National Park Service.
- O'Brien, Austin N. (April 1982). "National Register of Historic Places Registration:Patriot's Park". New York State Office of Parks, Recreation and Historic Preservation. Retrieved 2010-12-30.
- Genealogical and Family History of Southern New York and the Hudson River Valley (1913) Volume II, p.457
- Lossing, Benson John, The Pictorial Field-book of the Revolution. Harper & Bros., 1852. Online:  University of Michigan.
- Bolton, Robert, A History of the County of West Chester. Gould, Alexander S., 1848. Online:  Harvard University.
- Half Moon Press, "Cemeteries and Notable Burial Sites in Westchester County". NY, 2003. Online:  Hudsonriver.com.
- ed., The Builders of the Nation, National Cyclopaædia of American Biography. Stanley-Bradley Publishing Co., NYC, 1892. Online:  New York Public Library.
- Cray, Robert E. Jr., "Major John Andre and the Three Captors: Class Dynamics and Revolutionary Memory Wars in the Early Republic, 1780-1831", Journal of the Early Republic, Vol. 17, No. 3. Autumn, 1997. University of Pennsylvania Press.
- Raymond, Marcius Denison. David Williams and the capture of Andre: A paper read before the Tarrytown Historical Society Tarrytown: Argus - 1903 - approx. 35 pp.