Why are certain foreign policy options considered taboo or simply kept off the agenda as necessarily unthinkable or self-destructive? And under what conditions can governments transcend such “policy frontiers”? This article seeks to answer these questions by examining the circumstances that brought about Canada's and Mexico's entry into the North American Free Trade Agreement (NAFTA)—a move that constituted a surprising reversal of historic prohibitions on formalizing bilateral economic integration that had long been entrenched in these two nations' foreign policies. Policy frontiers develop as certain elements of the “national interest”—sovereignty, security, and identity—become equated with the legitimation of state elites. When these leaders defend the policy frontier (ostensibly to defend the nation), they are also defending their own political power. These barriers are constructed in a path-dependent fashion, through a critical juncture that first establishes the frontier, and then are maintained over time by institutional and ideological mechanisms of reproduction. For the frontier to be transcended, a critical juncture combining an exogenous shock with an internal legitimacy crisis must undermine, and then reconfigure, both mechanisms of reproduction. The origins of NAFTA in the Canadian and Mexican embrace of the once-forbidden bilateral free-trade option in 1985 and 1990, respectively, illustrate this dynamic, while the individual cases offer variations on the policy frontier model that can provide insights into the analysis of other cases of historically resisted foreign policy change.