From that charge he was promoted to the deanery of the High Kirk of Edinburgh (St Giles) on 12 July 1672, and was admitted a burgess and guild-brother of the city on 13 November 1673.

On 29 January 1688 he preached a thanksgiving sermon at Edinburgh for the queen's being with child, in which he mentioned that she often spent six hours at a time on her knees in prayer.

Among the papers of the Earl of Rosslyn at Dysart House there is a journal kept by Paterson in London in 1695–6, in which he records interviews with statesmen while seeking permission from William III of England to return to Scotland.

In that year he wrote a letter from Edinburgh to Henry Compton, Bishop of London, on the subject of toleration for the episcopal clergy.

He exerted himself in the following years, together with the other Scottish bishops, in endeavouring to obtain grants from the government for relief of poor clergymen, as well as some allowance for themselves out of the revenues of their sees.

It was the queen's intention that such grants should be made, but it was not carried into real effect, except with regard to Bishop Alexander Rose of Edinburgh and Paterson himself.

On 7 December 1704 Paterson and Bishop Rose, with others, accredited Dr. Robert Scot, Dean of Glasgow, as an agent to make collections in England.

He was favourably received, and obtained a promise of £1,600 annually, out of which George Lockhart of Carnwath charges him with securing £400 for himself, although he was then worth £20,000, or, as the Archbishop of Canterbury reported (according to Paterson's own statement), £30,000.