Maximal oxygen uptake (VO2max) is often used to assess an individual's cardiorespiratory fitness. However, measuring this variable requires an athlete to perform a maximal exercise test which may be impractical, since this test requires trained staff and specialized equipment, and may be hard to incorporate regularly into training programs. The aim of this study is to develop a new model for predicting VO2max by exploiting its relationship to heart rate and accelerometer features extracted during submaximal running. To do so, we analyzed data collected from 31 recreational runners (15 men and 16 women) aged 19-26 years who performed a maximal incremental test on a treadmill. During this test, the subjects' heart rate and acceleration at three locations (the upper back, the lower back and the tibia) were continuously measured. We extracted a wide variety of features from the measurements of the warm-up and the first three stages of the test and employed a data-driven approach to select the most relevant ones. Furthermore, we evaluated the utility of combining different types of features. Empirically, we found that combining heart rate and accelerometer features resulted in the best model with a mean absolute error of 2.33 ml ⋅ kg-1 ⋅ min-1 and a mean absolute percentage error of 4.92%. The model includes four features: gender, body mass, the inverse of the average heart rate and the inverse of the variance of the total tibia acceleration during the warm-up stage of the treadmill test. Our model provides a practical tool for recreational runners in the same age range to estimate their VO2max from submaximal running on a treadmill. It requires two body-worn sensors: a heart rate monitor and an accelerometer positioned on the tibia.