Accurate Energy Expenditure (EE) estimation is key in understanding how behavior and daily physical activity (PA) patterns affect health, especially in today's sedentary society. Wearable accelerometers (ACC) and heart rate (HR) sensors have been widely used to monitor physical activity and estimate EE. However, current EE estimation algorithms have not taken into account a person's cardiorespiratory fitness (CRF), even though CRF is the main cause of inter-individual variation in HR during exercise. In this paper we propose a new algorithm, which is able to significantly reduce EE estimate error and inter-individual variability, by automatically modeling CRF, without requiring users to perform specific fitness tests. Results show a decrease in Root Mean Square Error (RMSE) between 28 and 33% for walking, running and biking activities, compared to state of the art activity-specific EE algorithms combining ACC and HR.