There has been little comparative, cross-cultural research on sexual difficulties and associated distress, and factors associated with these, among older women. Therefore, the aim of this study was to investigate prevalence rates of sexual difficulties, distress related to these difficulties, and associated sociodemographic, relational, and health factors, among sexually active older women (60–75 years) in committed relationships across four European countries (Norway, Denmark, Belgium, and Portugal). These data could inform us about what differentiates women who do and do not experience distressing sexual difficulties and facilitate the identification of older women who might benefit from clinical interventions as well as the development of new interventions. In total, 1057 women (357 Norwegian; 322 Danish; 237 Belgian; 141 Portuguese) completed a cross-sectional questionnaire assessing six sexual difficulties—vaginal dryness, orgasmic difficulties, lacking interest in sex, lacking enjoyment in sex, pain during sex, and no excitement/arousal during sex—and associated distress. We found a high prevalence of sexual difficulties lasting 3 months or longer in the past year (between 23.5 and 50.2%, depending on the specific difficulty). With the exception of vaginal dryness and pain during sex, however, the majority of women reporting sexual difficulties (50.0% to 86.1%, depending on the specific difficulty) reported no or mild distress. There were relatively few cross-country differences, either in the prevalence of sexual difficulties or related distress. Few sociodemographic or health variables were associated with distressing sexual difficulties, but higher sexual intimacy, higher emotional intimacy, and better mental health were associated with less distress about some sexual difficulties. The findings underline the importance of healthcare professionals asking older women about sexual function and especially associated distress, and suggest that careful attention to the psychological and relationship context of these sexual difficulties is needed, as these could be important targets in the treatment process.