Stewart was educated at Chigwell School, followed by the Royal Military Academy Sandhurst near Camberley in Surrey. He spent part of his childhood in Cyprus.
Born to a father serving in the military, Stewart was selected for officer training at the age of seventeen, and after two years of training at RMA Sandhurst was commissioned into the Cheshire Regiment as a second lieutenant on 25 July 1969. He was promoted to lieutenant on 25 January 1971. In 1974 he undertook an in-service Bachelor's degree in International Politics at the University of Wales, Aberystwyth, graduating with first class honours. He was promoted captain on 25 July 1975. He guarded Rudolf Hess in Spandau Prison, Berlin.
From 1977 served in Northern Ireland both as intelligence officer and, after attending Staff College, Camberley and promotion to major on 30 September 1981, company commander of A Company 1 CHESHIRE, with an intermediate period spent at RMA Sandhurst as an instructor. During his time in Northern Ireland he was the Incident Commander at the Droppin Well bombing in Ballykelly which killed seventeen people. Stewart heard the explosion and arrived at the scene two or three minutes later. Six of the dead soldiers were from his company, including his clerk and storeman. He received a personal commendation from the General commanding in Northern Ireland for his actions on the day.
In 2017 he spoke of authorising now forbidden deep-Interrogation techniques during his time in Northern Ireland.
He served in the Ministry of Defence, and was second in command of an infantry battalion. He was promoted lieutenant-colonel on 31 December 1987, and served as a military attaché to the NATO military committee in Brussels. In March 1991 he assumed command of 1st Battalion, Cheshire Regiment, and as commanding officer returned to Northern Ireland for a further two operational tours and then became the first British Commander of United Nations forces in Bosnia from September 1992 to May 1993. It was as commanding officer in Bosnia, as part of Operation Grapple, that he earned the nickname "Bosnia Bob" and became something of a media personality. During his time in Bosnia he discovered the Ahmići massacre in which 103 people were killed. He was awarded the Distinguished Service Order on 12 June 1993 on his return to the United Kingdom. He was promoted colonel on 31 December 1993, and went on to take up the position of Chief of Policy at Supreme Headquarters Allied Powers Europe, before officially retiring from the army on 1 February 1996.
In 1997 Stewart took three weeks' leave from the public relations company Hill & Knowlton to help his friend Martin Bell who was standing for Parliament in Tatton as an Independent candidate. Stewart was alongside Bell when they were confronted by the sitting Conservative Member of Parliament for the constituency, Neil Hamilton and his wife Christine on Knutsford Heath. Bell, who was opposing Hamilton as a result of accusations that Hamilton had accepted money for promoting causes in Parliament, gave Stewart the credit for defining his criticism of Hamilton as having already admitted to "conduct unbecoming".
Since leaving the army Stewart has become a well-known commentator upon military and political affairs, frequently commenting upon the defence policy of the British Government and the wars in Afghanistan and Iraq. In 2009 he condemned the system compensating injured soldiers, accusing the MOD of acting with "the speed of a striking sloth". He also accused the government of repeatedly refusing the requests of army commanders for more troops and more helicopters in Afghanistan.
On 28 July 2009, it was revealed that he had been approved to put himself forward for selection to constituency associations as a PPC for the Conservative Party. As the former commander of the Cheshire Regiment he was linked to the safe Conservative East Cheshire seats of Macclesfield and Congleton, however the final shortlists for Macclesfield and for Congleton from Conservative Central Office did not contain his name. In summer 2009 he was shortlisted for Beckenham, one of the safest Conservative seats in the country, and on 6 December it was announced that he had been selected as Conservative candidate there, winning an overall majority on the second ballot.
At the 2010 general election on 6 May, Stewart was elected as the new MP for Beckenham.
Stewart served on the House of Commons Defence Select Committee and in May 2014 he was one of seven unsuccessful candidates for the chairmanship of the committee.
Stewart has been vocal in criticising cuts to the defence budget, suggesting in March 2015, that if the Joint Chiefs of Staff were to resign over the issue it would "make a very powerful message". When asked if he would resign as an MP himself, he said that he was considering it.
At the 2015 general election, he retained his seat. Stewart's seat is a target seat for the Liberal Democrats (fourth placed in 2015) following his support of Brexit.
In 2016, he was involved in an argument with the media following him describing female journalist Isabel Hardman as "totty"
At the snap 2017 general election, he retained his seat with an increased vote share of two percent.
He has six children and is currently married to Swiss former Red Cross worker, Claire Podbielski.