His first cousin, James Tallmadge, Jr., was a United States Congressman from New York (1817-1819), Lieutenant Governor of New York (1825-1826), and first President of New York University from its founding (which James had helped with) in 1831 until 1850. James's sister, another first cousin of Nathaniel, was Rebecca Tallmadge, who married Theodorus Bailey, a United States Congressman and United States Senator from New York, as well as postmaster of New York City. His first cousin, once removed was Benjamin Tallmadge, United States Congressman from Connecticut. Through the Tallmadge family, Nathaniel was a distant cousin of Ernest Hemingway and Ben Affleck.