In the 1800s, St. Andrews was an important port. Due to the condition of the roads in New Brunswick at the time, a railway was desired to bring goods to Quebec and the rest of the colony. A railway from St. Andrews to Quebec had been discussed as early as 1835, but the railway was delayed due to disagreements about where boundary with the United States was. Work was suspended until the 1860s.
The SA&Q was built as a narrow-gauge railway. It reached Woodstock in 1867, Andover in 1876, Grand Falls in 1877 (where a roundhouse was built) and Little Falls in 1878.
A storm in late February 1887 closed the line between Grand Falls and Little Falls for over six weeks.
The railroad bridge above Grand Falls was damaged by frost on April 24, 1896. It was out of service until August of the same year. On June 31, 1900 the bridge collapsed under the train from Edmundston.
The SA&Q became part of the New Brunswick Railway, which was itself leased to the Canadian Pacific Railway in 1882.