Sleep-related painful erection is a rare syndrome recognized by reports of painful nocturnal erection, an association between REM sleep and pain, and the absence of pain during wakeful sexual activity. Approximately 30 cases have been reported in the literature. We add two more cases, each of which seemed to be associated with severe sleep apnea. Treatment of the apnea with Continuous Positive Airway Pressure device lessened the symptom in both men. Implications of this association are discussed.