The team was first formed in 1983 to compete in a once-off post-season exhibition match in Mildura, and another once-off game was played in 1994. Since 2003, the team has played a regular biennial pre-season match against an Australian Football League (AFL) club; the only exception was in 2011, when the scheduled match was cancelled due to inclement weather. The matches are usually played in the Northern Territory, either at Marrara Oval in Darwin or Traeger Park in Alice Springs.
The team was formerly selected from the best available players from several leagues around Australia, however since 2007 no player from outside the AFL competition has been selected in the squad. The AFL promotes the concept as recognition of the indigenous Australians contribution to the national competition, with approximately one in ten AFL players identifying as an Indigenous Australian.
The AFL has been criticised for letting its clubs prevent the All-Stars from selecting its top Indigenous senior players, or for placing restrictions on their game time. Additionally, the competing club side often treats the match as a preseason practice match, such that winning the match is less important then developing young players or building match fitness prior to the regular season. Despite this, the match remains popular with spectators in the Northern Territory.
The best on ground for the Indigenous All-Stars is awarded the Polly Farmer Medal which is in honour of Graham Farmer.
As of 2015, the All-Stars have won six of the eight matches it has played. The record attendance for the match was 17,500, in the 2003 match against Carlton at Marrara Oval.
Until 2005 the All-Stars were sponsored by the Aboriginal and Torres Strait Islander Commission, who had naming rights over the team. After the abolition of ATSIC, the team was renamed from Aboriginal All-Stars to Indigenous All-Stars. Since 2006 the team has been sponsored by Qantas through the AFL Kickstart indigenous program.