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 Northern New South Wales' NBN State Football League. The club saw its first action on 20 March 1967 when they travelled 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 Northern NSW Soccer 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 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 was co-coached by Damien Smith and Robert Virgilli during the 2010 season, which was a disappointing one for Broadmeadow. They finished the season in 6th place a missed out on the finals. Broadmeadow were champions in the 2012 and 2014 NNSWF State Cup. 2014 was the last year that the NNSW Football State Cup was contested, being replaced by the FFA Cup from then on. On Tuesday 29 July 2014, Broadmeadow hosted the inaugural FFA Cup game against Brisbane Strikers at Magic Park. The game was won by Brisbane Strikers after going into extra time. The final score being 1–2 to Brisbane with Scott Pettit scoring the goal for Magic. On Wednesday 29 July 2015, Broadmeadow hosted Heidelberg United FC at Magic Park for the FFA Cup. Heidelberg defeated Broadmeadow Magic FC 3–1 with Scott Pettit being Magic's goalscorer. On 7 May 2016, Jon Griffiths reached 100 caps for the club. On Wednesday 25 July 2018, Broadmeadow beat Canberra FC 4-1 at Deakin Stadium to secure their first round of 16 place for the FFA Cup.
