Despite the recognition that newcomers’ ego networks facilitate their adjustment, little is known about changes in their ego-network structures over time and potential drivers for the network changes. Drawing on coevolutionary theory of network dynamics and integrating insights from research on socialization dynamics, we examine the change-related, reciprocal relationships between perceived supervisor behaviors—specifically support and undermining—and structural holes in newcomers’ ego networks (i.e., the extent to which newcomers connect otherwise disconnected individuals). Using latent change score (LCS) modeling in a longitudinal study of new employees, we found evidence of coevolution: perceived supervisor undermining hindered their development of ego networks with increasingly more structural holes; in turn, newcomers who spanned structural holes in their ego networks experienced increasingly more supervisor undermining. Additionally, those whose networks are rich in structural holes perceived increasingly less supervisor support over time. These findings have implications for research on socialization and structural holes.