Nuttall was born in the village of Long Preston, near Settle in Yorkshire and spent some years as a journeyman printer in England. Soon after going to the United States he met Professor Benjamin Smith Barton (1766-1815) in Philadelphia. Barton encouraged him to take up the study of the plants, and Nuttall began collecting plants for Philadelphia University.
In 1810 he travelled to the Great Lakes and in 1811 travelled with an expedition led by William Price Hunt on behalf of John Jacob Astor up the Missouri River. Nuttall was accompanied by the English botanist John Bradbury, who was collecting plants on behalf of Liverpool botanical gardens. Nuttall and Bradbury left the party at the trading post with the Arikara Indians in South Dakota, and continued further upriver with Ramsay Crooks. In August they returned to the Arikara post and joined Manuel Lisa's group on a return to St. Louis.
Although Lewis and Clark had travelled this way previously, many of their specimens had been lost. Therefore the plants collected by Nuttall on this trip were unknown to science. The imminent war between England and America caused him to return to London via New Orleans. In London he spent time organising his large plant collection and discussing his experiences with other scientists.
In 1815 he returned to America and after spending some more time collecting published The Genera of North American Plants in 1818. From 1818 to 1820 he travelled along the Arkansas and Red Rivers, returning to Philadelphia and publishing his Journal of Travels into the Arkansas Territory during the year 1819. In 1825 he became curator of the botanical gardens at Harvard University. He published his Manual of the Ornithology of the United States and of Canada (1832 and 1834).
In 1834 he resigned his post and set off west again, this time accompanied by the naturalist John Kirk Townsend. They travelled through Kansas, Wyoming and Utah, and then down the Snake River to the Columbia. Nuttall then sailed across the Pacific Ocean to the Hawaiian Islands in December. He returned in the spring of 1835 and spent the year botanizing in the Pacific Northwest, an area already covered by David Douglas. On his return trip he stopped off in San Diego, where he met Richard Henry Dana, Jr. The character of 'old curious' in Dana's book Two Years Before the Mast is based on Nuttall.
From 1836 until 1841 Nuttall worked at the Academy of Natural Sciences in Philadelphia. During this time he made contributions to the Flora of North America being prepared by Asa Gray and John Torrey. The death of his uncle then required Nuttall to return to England, as to inherit the property he had to remain for six months a year in that country. Between 1842 and 1849 he published his North American Sylva: Trees not described by F. A. Michaux, which was the first book to include all the trees of North America. He died in St Helens, Lancashire.
Various plants and birds were named for Nuttall, including Nuttall's Woodpecker by his friend William Gambel and Yellow-billed Magpie Pica nuttalli by John James Audubon.