Kinship is a fundamental and universal aspect of the structure of human society. The kinship category of 'grandparents' is socially salient, due to grandparents' investment in the care of the grandchildren as well as to older generations' control of wealth and cultural knowledge, but the evolutionary dynamics of grandparent terms has yet to be studied in a phylogenetically explicit context. Here, we present the first phylogenetic comparative study of grandparent terms by investigating 134 languages in Pama-Nyungan, an Australian family of hunter-gatherer languages. We infer that proto-Pama-Nyungan had, with high certainty, four separate terms for grandparents. This state then shifted into either a two-term system that distinguishes the genders of the grandparents or a three-term system that merges the 'parallel' grandparents, which could then transition into a different three-term system that merges the 'cross' grandparents. We find no support for the co-evolution of these systems with either community marriage organisation or post-marital residence. We find some evidence for the correlation of grandparent and grandchild terms, but no support for the correlation of grandparent and cross-cousin terms, suggesting that grandparents and grandchildren potentially form a single lexical category but that the entire kinship system does not necessarily change synchronously.