The club was founded on 9 April 1966 by Macedonian Australians as Newcastle Macedonia FC. Originally formed as a social club to play football together with other Macedonians, it is now a major force in News South Wales' NBN State Football League. The club saw its first action on 20 March 1967 when they traveled to Evans Park to face Cardiff Workers RSL. The hosts were upset however, with Macedonia winning the match, 2-1.
Throughout the years, Broadmeadow have gone through a series of name changes. The club was known as Broadmeadow United from 1971 until 1974 and then enjoyed a period of success in the 1970s as Hamilton Red Star. In 1975, Red Star was promoted to the NSW Football Federation 4th division, the 3rd division in 1976, the 2nd division in 1978 and finally the 1st Division in 1980. By 1985, Red Star was relegated back to the 2nd division, and had reverted to its original name, Newcastle Macedonia. During 10 years of competing in the 2nd division, Newcastle Macedonia won the league title twice.
In 1995, Newcastle Macedonia was finally promoted back to the highest flight in New South Wales, the NBN State Football League. The club made its final name change to its current, Broadmeadow Magic FC, but struggled in its first 2 years in the new league. Richard Hartley was appointed as the club's coach in 1997 who led the club to their first league title in the same year. Broadmeadow Magic remained successful in the first decade of the 2000s, as head coach Damien Smith led the club to their third league title in 2003, the club's first grand final title in 2004, and both titles in 2005. In recent years, Broadmeadow won its 5th league title in 2008, but disappointingly finished 3rd in the league in 2009.
Broadmeadow has produced a number of players who have gone on to play for the Newcastle Jets in Australia's number one domestic competition, the Hyundai A-League. Ben Kantarovski, one of Newcastle's key players and current captain of the Australian U/20 side, was a Broadmeadow Magic junior. Ben Kennedy, Newcastle's first-choice goalkeeper, was also a Broadmeadow junior, and Peter Haynes, who was in the Newcastle Jets squad for the 2009 AFC Asian Champions' League, currently plays for Magic. The club will be co-coached by Damien Smith and Robert Virgilli for the 2010 season.