Feedback of power during running is a promising tool for training and determining pacing strategies. However, current power estimation methods show low validity and are not customized for running on different slopes. To address this issue, we developed three machine-learning models to estimate peak horizontal power for level, uphill, and downhill running using gait spatiotemporal parameters, accelerometer, and gyroscope signals extracted from foot-worn IMUs. The prediction was compared to reference horizontal power obtained during running on a treadmill with an embedded force plate. For each model, we trained an elastic net and a neural network and validated it with a dataset of 34 active adults across a range of speeds and slopes. For the uphill and level running, the concentric phase of the gait cycle was considered, and the neural network model led to the lowest error (median +/- interquartile range) of 1.7% +/- 12.5% and 3.2% +/- 13.4%, respectively. The eccentric phase was considered relevant for downhill running, wherein the elastic net model provided the lowest error of 1.8% +/- 14.1%. Results showed a similar performance across a range of different speed/slope running conditions. The findings highlighted the potential of using interpretable biomechanical features in machine learning models for the estimating horizontal power. The simplicity of the models makes them suitable for implementation on embedded systems with limited processing and energy storage capacity. The proposed method meets the requirements for applications needing accurate near real-time feedback and complements existing gait analysis algorithms based on foot-worn IMUs.