His actual entry into the navy was probably in 1769, when he joined the Phœnix going out to the Guinea coast, with the broad pennant of his maternal uncle, Commodore George Anthony Tonyn.
In February 1781 Paterson joined the Sandwich, Rodney's flagship; went home with the admiral in the Gibraltar, and returned to the West Indies with him in the Formidable.
On arriving on the station in the end of February, he was appointed acting-captain of the St. Eustatius, armed ship, and on 8 April was promoted to command the Blast, in which he returned to England on the conclusion of the peace.
In 1797 he was inspecting captain of the quota men in Kircudbright and Wigtonshire, and in 1798 superintended the fitting of the Admiral de Vries, till she was turned over to the transport board.
He married, in 1801, Jane Ellen, daughter of his first cousin, David Yeats, formerly registrar of East Florida.