(1) Background: Ankle joint power, as an indicator of the ability to control lower limbs, is of great relevance for clinical diagnosis of gait impairment and control of lower limb prosthesis. However, the majority of available techniques for estimating joint power are based on inverse dynamics methods, which require performing a biomechanical analysis of the foot and using a highly instrumented environment to tune the parameters of the resulting biomechanical model. Such techniques are not generally applicable to real-world scenarios in which gait monitoring outside of the clinical setting is desired. This paper proposes a viable alternative to such techniques by using machine learning algorithms to estimate ankle joint power from data collected by two miniature inertial measurement units (IMUs) on the foot and shank, (2) Methods: Nine participants walked on a force-plate-instrumented treadmill wearing two IMUs. The data from the IMUs were processed to train and test a random forest model to estimate ankle joint power. The performance of the model was then evaluated by comparing the estimated power values to the reference values provided by the motion tracking system and the force-plate-instrumented treadmill. (3) Results: The proposed method achieved a high accuracy with the correlation coefficient, root mean square error, and normalized root mean square error of 0.98, 0.06 w/kg, and 1.05% in the intra-subject test, and 0.92, 0.13 w/kg, and 2.37% in inter-subject test, respectively. The difference between the predicted and true peak power values was 0.01 w/kg and 0.14 w/kg with a delay of 0.4% and 0.4% of gait cycle duration for the intra- and inter-subject testing, respectively. (4) Conclusions: The results of this study demonstrate the feasibility of using only two IMUs to estimate ankle joint power. The proposed technique provides a basis for developing a portable and compact gait monitoring system that can potentially offer monitoring and reporting on ankle joint power in real-time during activities of daily living.