Aim: To assess the prevalence and severity of sexual dysfunction in patients with multiple sclerosis and its associations with clinical, neuropsychological, and MRI-related factors, considering the primary, secondary, and tertiary components of sexual dysfunction. Materials and Methods: This cross-sectional observational study included 109 patients with multiple sclerosis (80 women, 73.4%; 29 men, 26.6%). Sexual dysfunction was assessed using the Multiple Sclerosis Intimacy and Sexuality Questionnaire-19 (MSISQ-19), including total and subscale scores. Cognitive function, fatigue, depression, and anxiety were assessed using the Symbol Digit Modalities Test (SDMT), Modified Fatigue Impact Scale (MFIS), Beck Depression Inventory (BDI), and Hamilton Anxiety Rating Scale (HAM-A), respectively. Spearman’s correlation analysis and the Mann–Whitney U test were used; p < 0.05 was considered statistically significant. Results: Clinically relevant sexual dysfunction was identified in 60 patients (55.1%). The total MSISQ-19 score correlated positively with age (ρ = 0.26; p = 0.016), EDSS (ρ = 0.40; p < 0.001), BDI (ρ = 0.36; p = 0.004), HAM-A (ρ = 0.57; p < 0.001), and MFIS (ρ = 0.64; p < 0.001) score. Brainstem lesions on MRI were associated with higher primary sexual dysfunction subscale score (median 11.0 vs. 8.0; p = 0.013). Conclusions: sexual dysfunction was common in patients with multiple sclerosis and was significantly associated with age, disability level, fatigue, depression, anxiety and brainstem lesions on MRI, supporting its multifactorial nature and the need for routine clinical assessment.