Paul Gray joined the Civil Service in 1969 as an economist at HM Treasury. During his time there he variously worked on agriculture, industry, and employment issues, and co-ordinated the Public Expenditure Survey process. Except for two years working for Booker McConnell Ltd in the late 1970s as a corporate planner, he remained at the Treasury until 1988, when he was appointed private secretary for economic affairs to the prime minister, Margaret Thatcher.

After two years, Gray returned to the Treasury in 1990, where he worked on monetary policy, serving as a member of the EU Monetary Committee. From 1995 to 1998 he was director of budget and public finances, taking overall responsibility for the Finance Bill process.

Gray transferred to the Department of Social Security (DSS) in 1998 as group director and head of policy. He played a major role in forming the Department for Work and Pensions (DWP), a department created by merging the DSS, the Employment Service, and parts of the former Department for Education and Skills. He later became Second Permanent Secretary and managing director, pensions and disability.^[2] Whilst at the DSS he was appointed to be a Companion of the Order of the Bath in the Birthday Honours List, 2000.^[1]

In September 2004, Gray was appointed deputy chairman of both the Inland Revenue and HM Customs and Excise, as those organisations prepared to merge following the O'Donnell Review. He was subsequently appointed as deputy chairman of HM Revenue & Customs. On 1 September 2006 Paul Gray was appointed acting chairman of HMRC, following the resignation of Sir David Varney (who moved to the Treasury). His position was confirmed as permanent in February 2007,^[3] until his resignation on 20 November 2007 following the loss of 25 million child benefit records.^[4]