Background: The problems in sexual functioning among patients with post-traumatic stress disorder (PTSD) are often overlooked, although scientific research confirms high rates of sexual dysfunctions (SD) particularly among veterans with PTSD. The main objective of this study was to systematically identify predictors of SD among veterans with PTSD. Methods: Three hundred veterans with PTSD were included in the cross-sectional study. The subjects were assessed by the Mini-International Neuropsychiatric Interview (MINI) and self-report questionnaires: PCL-5, i.e., PTSD Checklist for Diagnostic and Statistical Manual of Mental Disorders, Fifth Edition (DSM-5) with Criterion A, International Index of Erectile Function (IIEF), Premature Ejaculation Diagnostic Tool (PEDT), and Relationship Assessment Scale (RAS). Several hierarchical multiple regressions were performed to test for the best prediction models for outcome variables of different types of SD. Results: 65% of participants received a provisional diagnosis of SD. All tested prediction models showed a good model fit. The significant individual predictors were cluster D (Trauma-Related Negative Alterations in Cognition and Mood) symptoms (for all types of SD) and in a relationship status/relationship satisfaction (all, except for premature ejaculation (PE)). Conclusions: The most salient implication of this study is the importance of sexual health assessment in veterans with PTSD. Therapeutic interventions should be focused on D symptoms and intended to improve relationship functioning with the aim to lessen the rates of SD. Psychotropic treatment with fewer adverse sexual effects is of utmost importance if pharmacotherapy is applied. Appropriate prevention, screening, and treatment of medical conditions could improve sexual functioning in veterans with PTSD.