Physics-based predictive simulations of human movement have the potential to support personalized medicine, but large computational costs and difficulties to model control strategies have limited their use. We have developed a computationally efficient optimal control framework to predict human gaits based on optimization of a performance criterion without relying on experimental data. The framework generates three-dimensional muscle-driven simulations in 36 min on average—more than 20 times faster than existing simulations—by using direct collocation, implicit differential equations and algorithmic differentiation. Using this framework, we identified a multi-objective performance criterion combining energy and effort considerations that produces physiologically realistic walking gaits. The same criterion also predicted the walk-to-run transition and clinical gait deficiencies caused by muscle weakness and prosthesis use, suggesting that diverse healthy and pathological gaits can emerge from the same control strategy. The ability to predict the mechanics and energetics of a broad range of gaits with complex three-dimensional musculoskeletal models will allow testing novel hypotheses about gait control and hasten the development of optimal treatments for neuro-musculoskeletal disorders.