Communication between parents and their adolescent children has been identified as one of the potential protective factors for adolescent sexual health. Qualitative exploration of sexual health communication with adolescents aged 12-15 (N = 114) and a sub-group of the parents (N = 20) was carried out. Four major themes emerged: reasons for parent-adolescent communications, or lack thereof; the focus of parental messages; the moral of the message; and the barriers to communication between parents and adolescents. Findings revealed similarities and discrepancies in views and perceptions between parents and adolescents. Adolescents and parents suggested that some sexual health communication was happening. Parents were reportedly likely to use fear to ensure that their children do not engage in risky sexual activities, while adolescents reported that conversations with their parents were mostly ambiguous and filled with warnings about the dangers of HIV/AIDS. Several communication barriers were reported by parents and adolescents. Parents of adolescents would benefit from HIV/AIDS specific communication skills.