Fulton was born in Renfrewshire, Scotland, around 1780. He worked for John Rennie and for Thomas Telford, both of whom were noted engineers. In the case of the latter, his work included surveys of roads in the Scottish Highlands and in North Wales, as well as work in Sweden and, between 1809–1810, a survey of the Stamford Canal. It was while he was in Stamford, Lincolnshire, that he married Sarah Collins Martin, on 25 April 1810.
In 1815, Fulton journeyed to Bermuda on a commission from the Admiralty. There he reported on the development of naval constructions at the recently acquired dockyard on Ireland Island, Bermuda. He was similarly tasked at Malta in 1817, and both of these ventures were conducted under the instruction of Rennie.
Subsequently, Fulton met Peter Brown from North Carolina. Brown, who was a member of the state's General Assembly, had fruitlessly spent nearly a year in England, searching for a suitably qualified person to take on the role of state engineer. His search had been hampered by the unwillingness of potential candidates to leave their well-provided situations; Fulton, however, was at that time unemployed and agreed to take the post on a salary of £1200 per annum. Fulton's assistant, Robert H. B. Brazier, was also employed, on the lesser salary of £300. Fulton had been recommended for the post by Rennie and Telford.
The two men immediately set about their tasks. Fulton examined the coastal inlets, sounds and principal rivers with an eye toward practical improvements in navigation while Brazier conducted the surveys and made maps and plates thereof. As Chairman of the commission, Murphy prepared a memoir of the situation in the state for the information and instruction of Fulton. The first object in view being to render the rivers navigable, not for steamboats, but for flat boats, carrying produce from river landings down the stream to some lower point for shipment. To this end, the Catawba and Yadkin were deemed navigable almost to the mountains. Ashe declares that Murphy's notes to Fulton indicate such a thorough examination of detail and such a copious volume of information that Murphy himself must be considered possessed of considerable engineering acumen.
One of Fulton's first recommendations was the reopening of Roanoke Inlet which had been closed since 1795. His report thereon conveys a ready appreciation of Fulton's skill and understanding. He understood the necessity of avoiding any deleterious effect on natural vegetation as well as the natural and mechanical forces necessary to keep such an inlet open once it was re-established. The project failed to be realized, but it remained the basis for state planning until well into the 1840s.