Hall begann seine berufliche Laufbahn als Schuhmacher und Farmer, studierte dann aber Rechtswissenschaft in Buffalo. Dabei schloss er Bekanntschaft mit dem späteren US-PräsidentenMillard Fillmore, für den er in der Folge zunächst als juristischer Assistent arbeitete; später wurden beide Kanzleipartner, nachdem Hall 1832 als Anwalt zugelassen worden war.
Öffentliche Ämter
Nathan Hall wurde in Buffalo und im Erie County in zahlreiche öffentliche Ämter gewählt. 1846 wurde er Mitglied des Staatsparlaments von New York; im gleichen Jahr zog er für die Whig Party ins US-Repräsentantenhaus ein. Nach Ende dieser Legislaturperiode wurde er allerdings nicht erneut als Kandidat nominiert.
Er legte sein Ministeramt nieder, um Richter am Bundesbezirksgericht für den Norddistrikt des Staates New York zu werden. Dies blieb er bis zu seinem Tod im März 1874. Er wurde auf dem Forest-Lawn-Friedhof in Buffalo beigesetzt; in unmittelbarer Nähe befindet sich das Grab seines guten Freundes Millard Fillmore, der nur sechs Tage nach Hall verstarb.