Stephen Wall was born on 10 January 1947, son of John Derwent Wall and Maria Laetitia Wall (née Whitmarsh). He was educated at Douai School and Selwyn College, University of Cambridge (BA; Honorary Fellow, 2000). In 1975 he married Catharine Jane Reddaway, daughter of G. F. N. Reddaway, CBE and of Jean Reddaway, OBE, having one son.

Wall joined the Foreign and Commonwealth Office in 1968 and his diplomatic career included the following: Addis Ababa [Ethiopia], 1969-72; Private Secretary to the British Ambassador to France, 1972-74; First Secretary, FCO, 1974-76; Press Officer, No 10 Downing Street, 1976-77; Assistant Private Secretary to the Foreign Secretary [David Owen], 1977-79; First Secretary, Washington [United States], 1979-83; Assistant Head, later Head, European Community Department, FCO, 1983-88; Private Secretary: to Foreign Secretary, 1988-90; to the Prime Minister [John Major], 1991-93; Ambassador to Portugal, 1993-95; Ambassador and UK Permanent Representative to EU, Brussels [Belgium], 1995-2000; Head of European Secretariat, Cabinet Office, and EU Adviser to the Prime Minister [Tony Blair], 2000-04.