Background There has been rapid increase in time spent using Internet as a platform for entertainment, socialising and information sourcing. This study aimed to evaluate the relationship between duration of time spent using Internet for leisure, depressive symptoms, and psychological distress among Australian adolescents. Methods Depressive symptoms were indicated by the youth self-report module from the Diagnostic and Statistical Manual of Mental Disorders Version IV criteria, and psychological distress was measured by Kessler Psychological Distress scale. Internet use was self-reported based on use on an average weekday, and an average weekend day. Multivariate logistic regression models were used to examine the relationship between Internet use and mental health outcomes. Models were adjusted for potential confounders: age; relative level of socio-economic disadvantage, and body mass index. Results Adolescents were aged 11–17 years (M = 14.5 years, SD = 2.04 years). Greatest time spent using internet (≥7 h a day) was significantly associated with experiencing depressive symptoms among females (OR = 2.09, 95% CI = 1.16, 3.76, p < 0.05), and high/very high levels of psychological distress for male (OR = 2.23, 95% CI = 1.36, 3.65, p < 0.01) and female (OR = 2.38, 95% CI = 1.55, 3.67, p < 0.01) adolescents. Conclusions With current initiatives to improve health behaviours among adolescents to improve physical health outcomes such as overweight or obesity, it is imperative that the reciprocal relationship with mental health is known and included in such public health developments. Internet use may interact with mental health and therefore could be a modifiable risk factor to reach and improve mental health outcomes for this age group. Caution is advised in interpretation of findings, with some inconsistencies emerging from this evidence.