Stuart Newall (baptised as Stewart) was born in the parish of Durrisdeer, Dumfriesshire, Scotland, on 9 May 1843, the son of Thomas Newall, a tailor, and his wife, Anne Dalziel. Nothing is known of his early life. In January 1863 he emigrated to Australia, and after a brief sojourn in Victoria arrived in Port Chalmers, New Zealand, in May of the same year. Newall spent a few months unsuccessfully seeking gold on the West Taieri diggings, then enlisted as a private in the 3rd Regiment, Waikato Militia, in Dunedin on 2 December 1863. He performed convoy escort and garrison duty in south Auckland and Waikato, and rapidly rose through the ranks, becoming a colour sergeant in July 1864. In November 1865 Newall was promoted to staff sergeant and made regimental orderly-room clerk.
On 10 March 1868 Newall transferred, with the rank of sergeant, to the No 4 Division of the newly formed New Zealand Armed Constabulary. In January the following year his unit was transferred from Waikato to Wanganui where it joined Colonel George Whitmore's forces for what was to be the last campaign against Ngati Ruanui leader Titokowaru. Newall took part in the action at Otautu on 13 March, and also in the pursuit of Titokowaru and his followers through the dense south Taranaki bush.
The Armed Constabulary Field Force was transported to the Bay of Plenty in April 1869 for the campaign against Te Kooti. In May, Whitmore launched an invasion of the rugged Urewera country. Newall was involved in a number of the engagements in this difficult campaign. He was commissioned in the field as an acting sub-inspector on 10 June 1869, serving first with Major John Roberts's column and later under Lieutenant Colonel John St John.
Newall now began to assume positions of responsibility. During January and February 1870 he commanded a unit engaged in operations against Te Kooti around Tapapa in eastern Waikato. Between 1870 and 1875 he was in command of Armed Constabulary posts at Cambridge and elsewhere in Waikato. For some time he also acted as postmaster in Cambridge. In 1871 the government presented him with a gold watch in appreciation of his work in writing an important military report on the Waikato region. At Cambridge on 12 March 1872, Newall married Georgina Roberts, the younger sister of his close friend and fellow officer, John Roberts. Their happy marriage produced four daughters and a son before Georgina Newall's death on 22 June 1908.
Newall was commissioned as a captain in the New Zealand Militia on 17 August 1874 and in March 1875 was placed in command of the Armed Constabulary contingent charged with policing the newly opened Ohinemuri goldfield. Before returning to Waikato, in February 1876, he received a valedictory address expressing the gratitude of local residents. Until June 1879 Newall commanded a unit of the Armed Constabulary, building roads and bridges in southern Waikato. He then led a party of Armed Constabulary to Taranaki as part of the concentration of government forces confronting Te Whiti-o-Rongomai. During the occupation of Parihaka on 5 November 1881 Newall was one of the two officers responsible for arresting Te Whiti, Tohu Kakahi and Hiroki.
Newall remained in Taranaki until the end of 1882. In January 1883 he was appointed adjutant to the Canterbury Volunteer District, and transferred to the permanent staff of the New Zealand Militia. In his new position, Newall assisted with the training and administration of local volunteer units. A capable and hard-working adjutant, he was promoted to major on 21 April 1885, and on 18 January 1891 to lieutenant colonel. The following April he took command of the Wellington, Wairarapa, Taranaki and Wanganui districts.
Newall became involved in the dog tax confrontation in the Hokianga district in 1898. Te Mahurehure hapu of Nga Puhi, under their leader Hone Toia, were threatening to forcefully oppose imposition of the tax. On 1 May 1898 Newall was dispatched to Hokianga with a force of Permanent Militia to arrest Hone Toia and suppress any disturbances. After arriving at Rawene on 3 May, Newall prepared his force of 120 men to move against the principal Te Mahurehure base in the nearby Waima River valley. At the same time, however, he was in close touch with other Maori leaders who were intent on preventing armed conflict. Newall's force advanced over the hills to the Waima valley on 5 May. Te Mahurehure had prepared an ambush, but at the last moment Hone Toia decided to refrain from violence. After much debate Hone Heke, MHR for Northern Maori, convinced Hone Toia and his supporters to surrender to Newall, who was greatly relieved that he was able to resolve the incident without bloodshed.
Between March and December 1900 Newall commanded the Fifth Contingent in South Africa. They frequently clashed with Boer commandos, and on 5 September a force led by Newall successfully ambushed a small Boer party. Newall relinquished command of the contingent in December 1900 and returned to New Zealand to resume his command of the Wellington district. For his services in South Africa Newall was mentioned in dispatches and in 1901 made a CB.
In January 1902 Newall was given the brevet rank of colonel. Only a year later he was abruptly retired, probably on grounds of age, and transferred to the Honorary Unattached List of the New Zealand Volunteer Force with the rank of colonel. He was still a vigorous man, and in April 1903 he became the secretary of the Wellington Commercial Travellers' and Warehousemen's Club. He was a popular secretary, and held the position until he resigned in March 1911. During the general strike of October–December 1913 Newall commanded the force of mounted special constables concentrated in Wellington. In December 1915 he was appointed commandant of King George V Hospital in Rotorua. More than 40 years of service in the New Zealand armed forces ended on 1 June 1918 when he relinquished this post. He then went to live with a married daughter in Waihi, where he died on 3 August 1919.
Stuart Newall's career encapsulates the changes in the organisation and role of New Zealand's fledgeling army. He played a significant part in these changes as a capable military commander and a meticulous and extremely conscientious administrator. He held Maori in high regard, once remarking that if he had been born a Maori he would have been a 'turbulent rebel', and that the Maori could teach the Pakeha a great deal about 'fortitude and forbearance'. Newall was a modest, intelligent man with a friendly, charming personality. His kindness and great concern for the welfare of others were always evident. A close friend, Gilbert Mair, stated that his 'radiant personality was a blessing' to his friends.