Prior research on network embeddedness suggests that relational embeddedness (i.e., the duration of previous alliances between two firms) and structural embeddedness (i.e., the number of partners common to both firms) facilitate alliance formation between firms. This study examines the opposite case—namely, the inhibition of alliance formation by relational and structural embeddedness. In this study, by considering these two types of embeddedness as drivers of partner choice sets, I propose that a choice set larger than a certain threshold size with sufficiently low variation in terms of the embeddedness of their options (i.e., relationally or structurally embedded potential partners) enables firms to recognize multiple options within the choice set. I also suggest that this in turn increases firms’ uncertainty about these options’ resources and reliability and inhibits the formation of alliances with them. These predictions are supported by empirical tests of code-share alliance data in the global airline industry from 1994 to 2006.