This study aimed to know the stages of behavior change of parents in relation to communication held with their adolescent children on sex, sexuality and HIV/Aids prevention. Prochask and Diclement' stages of change model was used. Interviews were carried out with 26 parents of adolescents from a public school in Fortaleza, CE, Brazil. Parents were classified according to the stages of change. The majority of them reported talking to their children about the issue or intending to do it, though some of them faced difficulties in doing so. The promotion of further information about HIV/Aids prevention and unwanted pregnancies is needed. Strategies should be developed jointly with families, schools and health services in order to promote better communication in the context of adolescents' family, towards a healthier sexual life for the adolescents.