We study gene family coevolution on a tree of life based on a large-scale ancestral gene content reconstruction, which includes gene duplication and deletion events. The insights obtained from this study are threefold: (1) Global properties, such as the distribution of coevolution partners and the formation of disconnected clusters of coevolving families, can be an inevitable consequence of evolution along a tree. (2) Concerted family expansion (gene duplication) and contraction (gene deletion) reflect functional constraints and therefore lead to better function prediction. (3) “Long-range” coevolutionary relationships, caused mostly by large family expansions or contractions, reveal high-level evolutionary organization of cellular processes in prokaryotes.