Restieaux left England in the Barque Cromwell soon after the Chartist Riots in London and arrived in South Australia in August 1848 or 1849. He worked on sheep stations and engaged in exploration for gold in South Australia and Victoria. At one time he spent two weeks in the company of 3 bushrangers, who were on the run from the police after a robbery of gold. It is possible that this was the party of bushrangers, led by John Francis, who held up the Private Escort Company's regular escort of gold from the McIvor diggings at Heathcote and Kyneton on the morning of 20 July 1853.
Restieaux spent time in Peru where he participated in a revolution. Later he sailed to San Francisco, where he joined a party of teamsters who crossed the mountains and plains to reach Salt Lake City. He later prospected near Nevada City, California.
In 1867 Restieaux was foreman of a Guano excavation operation at McKean Island, in the Phoenix Islands (which is now part of Kiribati). Towards the end of 1867 he was a passenger on the brig Kamehameka going to Honolulu for a vacation. At this time Ben Pease was the captain of the schooner the Blossom and trading in coconut and coconut oil in the Marshall Islands. As trading was good, in late 1867 Pease sent George Bridges, his mate, to Honolulu to ask Mr. C. A. Williams, the owner of the Blossom, to supply another schooner and to engage someone to take charge of the trading station at Ponape atoll (now known as Pohnpei). Williams engaged Restieaux for the position on Ponape and sent the schooner Malolo under Captain Bridges. The Malolo arrived at Mili Atoll on 1 March 1868. Instead of going to Ponape, Restieaux was put in charge of the Mili station. After nine months Williams sold his firm to Glover Dow & Co. of Shanghai. Mr. Williams wrote to Restieaux telling him he was to look to Glover Dow & Co for his pay – Restieaux was never paid as the company became insolvent.
Restieaux then traded as agent for Ben Pease on Ponape atoll, although that venture failed. In August 1871 Restieaux sailed with Bully Hayes on the Leonora and landed on Pingelap atoll where he traded as agent for Hayes until May 1872. Bully Hayes gave Restieaux a promissory note payable three months from date – this was never paid. Restieaux sailed with Hayes through the Gilbert Islands (now known as Kiribati) and arrived in Samoa in December 1872. He met Louis Beck, who travelled with Hayes on the Leonora; Beck's later published stories helped to build the mythic history of Bully Hayes.
Restieaux left Samoa in 1873 to trade at Nukufetau in the Ellice Islands (now known as Tuvalu). At the end of 1874 or early in 1875 HMS Rosario, under Commander Challis, came to Nukufetau looking for Hayes, while engaged in anti-blackbirding operations. Restieaux said that Hayes could be in the Marshall Islands. HMS Renard, under Captain Pugh, came to Nukufetau in 1876, again in search of Hayes.
In the 1870s J. C. Godeffroy und Sohn of Hamburg (operating out of Samoa) began to dominate the Tuvalu copra trade. In 1879 Restieaux was J. C. Godeffroy's resident trader at Nanumea, the northern atoll of Tuvalu. In the same year J. C. Godeffroy und Sohn was taken over by Handels-und Plantagen-Gesellschaft der Südsee-Inseln zu Hamburg (DHPG). From about April 1880 Louis Becke was on the nearby island of Nanumanga until the trading-station was destroyed later that year in a cyclone. Restieaux provided a description of Beck: “he was first rate company, a good storyteller or as poor Jack Buckland put it, Louis Beck was a first class liar."
During the 1880s, Restieaux continued with DHPG until that company ceased operating in the Ellice Islands. Restieaux moved to Funafuti in July 1881. Later that year George Westbrook arrive on Funafuti to trade as agent for Henderson and Macfarlane, they remained friendly competitors. In about 1888–89 Restieaux went to live in the southern atoll of Nukufetau, the home island of his wife Litia.
In 1890 Restieaux met Robert Louis Stevenson, his wife Fanny Vandegrift Stevenson and her son Lloyd Osbourne during their voyage on the Janet Nicoll, a trading steamer owned by Henderson and Macfarlane of Auckland, New Zealand, which operated between Sydney, Auckland and into the central Pacific. Fanny records that they made landfall at Funafuti, Niutao and Nanumea; however Jane Resture suggests that it was more likely they landed at Nukufetau rather than Funafuti. An account of this voyage was written by Fanny Vandegrift Stevenson and published under the title The Cruise of the Janet Nichol, together with photographs taken by Robert Louis Stevenson and Lloyd Osbourne.
In 1892 Captain Davis, of HMS Royalist, recorded Alfred Restieaux and Emile Fenisot as living on Nukufetau. From 1900 the numbers of palagi traders in Tuvalu declined so that by 1909 there were no resident palagi traders representing the trading companies. Restieaux died on Nukufetau in 1911.