Insufficient physical activity is a common problem for university students because they may engage in sedentary lifestyle owing to excessive time spent on their smartphones and social media use. This may result in problematic internet use (PIU) and nomophobia (fear of not having a mobile phone). Moreover, prior evidence shows that weight-related self-stigma is an important factor contributing to low physical activity. Therefore, the present study examined the associations between PIU, nomophobia, and physical activity among university students across mainland China, Taiwan, and Malaysia. Participants (3135 mainland Chinese, 600 Taiwanese, and 622 Malaysian) completed the Bergen Social Media Addiction Scale (BSMAS), Smartphone Application-Based Addiction Scale (SABAS), Nomophobia Questionnaire (NMPQ), Weight Self-Stigma Questionnaire (WSSQ), and International Physical Activity Questionnaire Short Form (IPAQ-SF). The measurement invariance of the assessed questionnaires was supported across the three regions. The present findings analyzed using partial least squares structural equation modeling showed that (i) greater nomophobia was associated with higher levels of physical activity, (ii) greater weight-related self-stigma was associated with higher levels of physical activity, and (iii) greater nomophobia was associated with greater weight-related self-stigma. Although the present findings suggest the possibility that experiencing some level of nomophobia or weight-related self-stigma appears to help improve physical activity, it is not recommended that these be encouraged, but reducing PIU should be targeted as a means to improve physical activity.