This exploratory case-based study investigates the development of project management (PM) as an organisational capability in two public sector organisations (PSO) during a period of rapid environmental change. Within the PM literature, the concept of project management capability (PMC) and how it develops over time through organizational learning is still an emerging tradition led to date by mainly European scholars (Lindkvist, Söderlund, Davies, Brady, Hobday, etc.). This investigation locates itself within this emerging tradition and represents a unique empirical opportunity to study the learning processes involved in PMC development in a complex setting that shows these processes in greater relief. In both of the organizations studied, the elevation and enhancement of PMC from a relatively low-level activity to a strategic supporting competence was triggered by radical and rapid change in the external environment during the 2000s. The main process insight is that PMC is found to be developed as a dynamic organisational capability in complex PM settings through organisational complex problem-solving (CPS). The overall outcomes of the study build upon and extend the emerging PMC literature in at least three important respects, with implications for traditional PM research and practice. Firstly, in contrast to the mechanistic view of traditional PM, this study supports an integrated knowledge-based view of ‘projects as process’ and ‘PM as practice’. In this view, a project is seen to be ‘a mode of organising to accomplish a temporary undertaking’ and PMC is seen as a strategic organisational practice in organising complex projects. Secondly, PMC is honed as a practice through goal-directed organisational CPS. This builds upon and extends the work of Popper on the evolutionary growth of knowledge by revealing problemsolving as a two-stage process of differentiation-integration, or disorder-order. In contrast to traditional PM which follows a path from ‘order to order’, the development of PMC as an organisational capability is found to proceed from ‘order to disorder to order’. Thirdly, using the lens of PM as practice, a 'distributed organising' approach is suggested for coordinating the formation of ‘complex knowledge’ under organisational CPS, which is inherently emergent and dynamic. This contrasts with the ‘centralised planning’ approach of traditional PM, which assumes that knowledge is manifest in pre-given plans that are executed with little organisational learning expected beyond the application of prior knowledge.