Routines and organizational capabilities are central constructs in explanations of firms’ heterogeneity and sustained competitive advantage in industries and markets. Building on the foundational contribution of Nelson and Winter, the routines and knowledge capabilities of firms have been a major focus of theorizing in many areas within innovation and management research. Despite this, numerous issues still remain unresolved, particularly regarding the specific mechanisms by which capabilities emerge and develop over time. In this paper, we contend that the evolutionary approach to the firm pioneered by Nelson and Winter can resolve existing contentious issues about the topic by adopting a complexity perspective. In particular, we argue that a view of the firm as a complex adaptive system enhances evolutionary explanations of the origin of organizational capabilities, and how these emerge and change via processes of organizational learning. In addition, we show that embedding this view within a general evolutionary framework emphasizes the role of knowledge capabilities as sources of developmental variety in the evolution of firms, and allows accounting for their creation via self-organizing processes as a fundamental dynamic force in economic evolution.