150 years after Darwin's seminal theory, there are many aspects of biological evolution that remain fascinatingly mysterious. We still have little understanding of its powers and limits: how complex is the functionality that biology can evolve? Recent work by Leslie Valiant and colleagues on viewing evolution as a form of computational learning from the environment has been able to obtain (based on a number of simplifying assumptions) certain bounds on the complexity of the genetic circuits that can evolve within feasible quantities of time and resources. Here we will go over the key concepts behind these results, and discuss possible connections to more established notions in evolutionary biology: especially modularity and evolvability, which are thought to be key organising principles of biological systems. In particular, we speculate on the link between two notions of ‘evolvability’: the evolvability of a system in terms of how agile it is in responding to novel goals or environments, and the evolvability of certain kinds of gene network functionality in terms of its computational complexity. Drawing on some recent work on the complexity of graph-theoretic problems on modular networks, we suggest that modularity as an organising principle may have its raison d’etre in its ability to enhance evolvability, in both its senses.