Nuttall was born in San Francisco, California, on 5 July 1862; the second son of Robert Kennedy Nuttall, M.D. (Aberdeen) and his wife, Magdalena, daughter of John Parrott of San Francisco. The Nuttalls were descended from an old Lancashire family, which settled in Ireland in 1707, many of its members serving as officers in the British Army. His father went to Australia, but migrated to San Francisco in 1850 and practised there till 1865. In that year the family came to Europe and remained there till 1876, the children being educated in England, France, Germany and Switzerland. Consequently, Nuttall spoke several languages, a fact which assisted him enormously in his future work and travels.