Critical security advocates generally assume that the process of broadening and deepening security starts with a core, the defence of state borders, which is progressively left behind or complemented by “non-state” concerns and “non-military” policies. They see this incorporation of economic, societal and environmental issues to security as a conceptual and policy innovation, which downplays and even puts into question the centrality of the military. In this paper, we seek to challenge this Western-centric interpretation by exploring the state and military sources of the comprehensive conception of security in Indonesia and Malaysia. Despite their differences in state building and international alignments, they both adopted comprehensive conceptions of security right from the start. Political, societal and economic issues have been constituted as security issues before the consolidation of frontiers and sovereignties.