As border management continues to be a contentious and fast developing policy area in the EU, a better understanding of FRONTEX is needed. This article takes the new institutionalist approach that the functioning of institutions is dependent on the conditions under which they emerge. Drawing on documentary resources and semi-structured interviews with EU officials, the article traces the process leading to the establishment of FRONTEX. It argues that a proper understanding of agency creation and design requires us to look beyond rational choice institutionalist explanations and take into account social processes and historical contexts. Expectations derived from the three main strands of new institutionalism (rational choice institutionalism, sociological institutionalism and historical institutionalism) are not mutually exclusive and can function as conceptual lenses drawing attention to different aspects of agency creation.