In the 1950s until 1963 Sabah competed as North Borneo football team in the Borneo Cup together with Sarawak football team and Brunei national football team. The North Borneo Football Association (NBFA) changed its name to Sabah Football Association (Sabah FA). Sabah qualify into the Malaysia Cup for the first time in 1977 and enter the competition in 1978.
Sabah was a well known team during the Malaysian football amateur and semi-pro era as state team produced many quality players namely the trio of James Wong, Hassan Sani and Peter Rajah. These players during their time led Sabah to become one of Malaysian football's most feared teams during the 80's.
One fine example was during the 1979 Malaysian League where Sabah started slowly. After a run of 8 matches, they stood with 3 wins, 2 draws and 3 losses but, during the later stages they stepped up a gear or five by winning all their remaining 8 matches with most of them by huge margins, including an incredible 8–0 thrashing of Sarawak, 11–0 hammering of Perak FA and the 6–1 beating of Terengganu FA. At the end of the season, Sabah finished as runners-up behind Singapore FA and became the highest scoring team with 49 goals in 12 games, which is an average of 3 goals per game.
In 1991, Sabah striker Matlan Marjan became the first Malaysia to score a double against England in 'A' international matches on 12 June 1991.