Originally called the Nickel Nouméa Sports Association (Nouméa ASLN), the club experienced its first period of glory in the late 1960s and 1970s. Winner of the New Caledonia Cup for four successive years between 1969 and 1972, followed by a 1975 win, the team was also a finalist in 1968, 1974, 1976 and 1977. Under the new name of A.S. Magenta, the club gradually returned to the forefront of the New Caledonian football scene in the early 1990s. Cup finalist in 1991, the team won again in 1996, followed by a series of six straight wins between 2000 and 2005, making it the most successful team in the competition.
AS Magenta won the Championship in 2003, 2004 and 2005. ASM was also champion of The Overseas Football Cup by beating AS Pirae in 2003 (2–2 in the first leg, 2-2 then the second leg, 4-3 after penalty shootout). AS Magenta season in the 2005 season, in addition to winning the cup and the championship of New Caledonia, reached the final of the OFC Champions League in June 2005 after finishing Group B in the top spot. However, the Caledonians bowed to the Australian team Sydney FC (0–2). The 2006 season is much less successful for AS Magenta. In addition to being eliminated before the finals of the OFC Champions League, the club also failed to win the title of champion of New Caledonia for the first time in four years, on top of failing to win the New Caledonia Cup for the first time since 1999.
In the 2007 season, under the coaching of former footballer André Bodji, the team won the championship three years in a row. Following the 2010 win, the team played in the 2010–2011 Coupe de France, becoming the first New Caledonian club to pass the seventh round of the preliminary phase, before being beaten in the eighth round by Paris FC (4-0).
In November 2014, the club won for the ninth time the New Caledonia Cup, after beating rivals AS Lössi 3–1, ensuring its place in the seventh round in the Coupe de France.