Newstead was born in Swanton Abbott, Norfolk where his father worked as a butler to Boulton of Oulton Hall.
His father later became a gardener at Sedgeford and young Newstead was introduced early to the world of plants and natural history.
Walker paid for his studies and encouraged him to work at the newly founded Grosvenor Museum, Chester.
For some time, Newstead worked as an assistant to Eleanor Ormerod, helping her compile lists of injurious insects for her annual reports.
Newstead also took an interest in archaeology, especially working on the digs to examine the Roman remains in Chester between 1926 and 1929.