Nathan Kelsey Hall was born in 1810 in Marcellus (now a part of Skaneateles), New York. After working as a shoemaker and farmer, Hall turned his attention to the law, studying under the direction of Buffalo attorney Millard Fillmore. Hall was admitted to the state bar in 1832 and joined Fillmore’s practice as partner.

Hall also became involved in local politics, serving as deputy clerk of Erie County, as clerk of the Board of Supervisors, and as member of the Board of Aldermen of Buffalo. In 1839, New York governor William Henry Seward appointed Hall as a mastery of chancery -- essentially a judge of the court of chancery. Two years later, Hall was elected judge of the Court of Erie County, where he served until 1845. In 1846, Hall was elected both to the New York State assembly and to the United State House of Representatives as a Whig, but, in 1848, chose not to run for reelection to the latter.

Following the death of President Zachary Taylor in 1850, new President Millard Fillmore tapped Hall to become his postmaster general. A close adviser to the President, Nathan Kelsey Hall served as postmaster until 1852, when he resigned to become judge of the United States Court for the Northern District of New York. Hall held that position until he died in 1874.