Background: Receiving timely health screening is associated with important public health benefits among older adults. By focusing on the role of social relationships, the present study was aimed at examining longitudinal trajectories of health screening use among older adults in Korea, whose universal health care system provides free-of-charge health screening. Methods: A nationally representative sample of 3,575 individuals aged 65 or older from wave one of the Korean Longitudinal Study of Aging (2006) was followed for 10 years (up to Wave 6, 2016). Mixed-effect logit models were used to investigate how an older adult's social relationship characteristics (i.e., household composition, financial support from family, social group participation, and the frequency of contact with friends or relatives) were associated with their trajectories of participation in the national health screening program. Results: Despite the low financial burden, only 49.7% of older adults in Korea reported receiving the recommended health screening at the baseline. Although the probability of receiving recommended health screening increased over the 10-year study period, the trajectories were significantly different by an older adult's social relationship characteristics. All four social relationship characteristics were significantly associated with receiving health screening. However, those with more frequent social contacts and those who participated in social groups showed steeper increases in the probability of receiving health screening (i.e., significant interaction with time). Conclusions: This study highlights the importance of social relationships and intervention approaches that accommodate socially isolated older adults to facilitate their timely receipt of recommended preventive care.