Introduction: Japan is assumed to have serious health and social problems due to Internet overuse, but little is known about the actual conditions. This study was conducted to investigate the prevalence of problematic Internet use (PIU) and associated Internet use in adolescents in Japan. Methods: A nationwide survey of adolescent Internet use was conducted in 2012 and 2013. The participants were 100,050 students from randomly selected junior and senior high schools nationwide who gave valid responses to a self-reported questionnaire. The questionnaire included questions on Internet use and the Japanese version of the Young's Diagnostic Questionnaire (YDQ) as well as other questions related to lifestyle habits. Internet users were classified by gender according to three categories on the basis of their YDQ scores: adaptive use, maladaptive use, and PIU. Results: The estimated prevalence of PIU was 6.2% in males, 9.8% in females, and 7.9% in total; it closely correlated with female gender, school grades, and number of Internet hours. The following common and gender-specific applications that conferred a risk of PIU were identified: downloading (both genders), online gaming (males), social networking services, blogs, and bulletin boards (females). Conclusions: A cross-sectional survey using YDQ of a large number of high school students yielded a PIU prevalence of 7.9% in Japan. This study showed that problems associated with Internet overuse have already become serious; therefore, planning and implementation of prevention and control measures is urgently required.