Although resource dependence theory (RDT) acknowledges that managing dependence relations with external organizations creates a dilemma for dependent firms who must decide between strengthening existing or exploring new resource domains, our understanding of when firms prioritize one action over the other is limited. Building on RDT’s premise that dependence relationships are initiated by executives, we argue that chief executive officer (CEO) turnovers within customers represent a critical uncertainty that increases dependent firms’ exploration of new domains (i.e., search breadth) and decreases exploitation of existing domains (i.e., search depth). Further, we argue that relationship length and CEO succession, as factors influencing dependence stability, moderate the effect of CEO turnover on these actions. We find support for our theorizing in a sample of firms with major customers.