Physical activity typically decreases during teenage years and has been identified as a health priority by Aboriginal adolescents. We examined associations between physical activity levels and sociodemographic, movement and health variables in the Aboriginal led ‘Next Generation: Youth Well-being (NextGen) Study’ of Aboriginal people aged 10–24 years from Central Australia, Western Australia and New South Wales. Baseline survey data collected by Aboriginal researchers and Aboriginal youth peer recruiters from 2018 to 2020 examined demographics and health-related behaviours. Logistic regression was used to estimate odds ratios (OR) for engaging in high levels of physical activity in the past week (3–7 days; 0–2 days (ref), or ‘don’t remember’) associated with demographic and behavioural factors. Of 1170 adolescents, 524 (41.9%) had high levels of physical activity; 455 (36.4%) had low levels; 191 (15.3%) did not remember. Factors independently associated with higher odds of physical activity 3–7 days/week were low weekday recreational screen time [55.3% vs. 44.0%, OR 1.79 (1.16–2.76)], having non-smoking friends [50.4% vs. 25.0%, OR 2.27 (1.03–5.00)] and having fewer friends that drink alcohol [48.1% vs. 35.2%, OR 2.08 (1.05–4.14)]. Lower odds of high physical activity were independently associated with being female [40.2% vs. 50.9%, OR 0.57 (0.40–0.80)] and some findings differed by sex. The NextGen study provides evidence to inform the co-design and implementation of strategies to increase Aboriginal adolescent physical activity such as focusing on peer influences and co-occurring behaviours such as screen time.