This study aims to determine the prevalence and factors associated with cyberbullying and social media addiction. This cross-sectional study was conducted among 270 medical students from a public university in Kuching, Malaysia. The instruments used in this study included the cyberbullying questionnaire survey, Bergen Social Media Addiction Scale (BSMAS), and the Depression Anxiety Stress Scale 21-item (DASS-21). The prevalence of cyberbullying victimization was 24.4%, whilst 13.0% reported cyberbullying perpetration over the past six months. Male gender was positively associated with both cyberbullying perpetration and cybervictimization, whilst social media addiction was positively associated with cybervictimization. Psychological motives such as positive attitudes toward cyberbullying and gaining power were associated with cyberbullying perpetration. Cybervictimization doubled the tendency to depression (aOR 2.50, 95% CI [1.23, 5.08], p = 0.012), anxiety (aOR 2.38, 95% CI [1.29, 4.40], p = 0.006), and stress (aOR 2.85, 95% CI [1.41, 5.77], p = 0.004), whilst social media addiction was associated with a higher tendency to depression (aOR 1.18, 95% CI [1.10, 1.26], p < 0.001), anxiety (aOR 1.15, 95% CI [1.08, 1.22], p < 0.001), and stress (aOR 1.21, 95% CI [1.12, 1.32], p < 0.001). Medical schools in Malaysia need policies and guidelines against cyberbullying.