Purpose Insufficient physical activity (PA) and inadequate sleep quality (SQ) and sleep duration (SD) are highly prevalent behaviors that increase the risk of developing many chronic health conditions. Evidence regarding bidirectional relationships between PA, SQ, and SD is inconsistent. As changes in one of these behaviors may impact on the other, it is important to understand the nature of the bidirectional relationship between PA and sleep. Therefore, the aim of this study was to examine the relationship between changes in PA, SQ, and SD over a 2-yr period in middle-age adults. Methods Participants were adults age 42 to 72 yr from Brisbane, Australia. Mail surveys were used to assess PA, SQ, SD, sociodemographic and health characteristics in 2011 and 2013 (n = 3649). Multinomial logistic regression analyses were conducted to examine the relationships between patterns of change in PA, SQ, and SD over the 2 yr. Results Improving or maintaining good SQ was associated with increasing or maintaining PA and maintaining PA was associated with maintaining or increasing SQ (P < 0.05). Changes in PA were not associated with changes in SD. Conclusions A bidirectional relationship between PA and SQ was identified; however, no evidence of a relationship in any direction between PA and SD was found. Multibehavior interventions targeting both PA and SQ are warranted. Middle-age adults with poor SQ may benefit from increasing PA and improving SQ may promote higher levels of activity.