While scholars have focused extensively on the consequences of partnerships between interest groups, less attention has been paid to the historical dynamics shaping when, how, and why such groups unite. This is especially true of “unexpected” partnerships, which unite groups with seemingly little in common. Such partnerships are important, as they can reshape to an unusual degree which actors, issues, and ideas “fit together” politically. We address the puzzle of how unexpected group partnerships form through case studies of previously non-existent alliances between labor unions and the gay/lesbian rights movement in the United States and United Kingdom in the 1970s and 1980s. Using these cases, we produce a theory arguing that unexpected partnerships are a product of a favorable political opportunity structure—present when each group experiences shared threats and mutual vulnerabilities—and the actions of entrepreneurial group leaders, who forge cross-group identities, accentuate shared ideological convictions, and build institutional ties.