The use of wearable sensors coupled with the processing power of mobile phones may be an attractive way to provide real-time feedback about physical activity and energy expenditure (EE). Here we describe use of a shoe-based wearable sensor system (SmartShoe) with a mobile phone for real-time prediction and display of time spent in various postures/physical activities and the resulting EE. To deal with processing power and memory limitations of the phone, we introduce new algorithms that require substantially less computational power. The algorithms were validated using data from 15 subjects who performed up to 15 different activities of daily living during a four-hour stay in a room calorimeter. Use of Multinomial Logistic Discrimination (MLD) for posture and activity classification resulted in an accuracy comparable to that of Support Vector Machines (SVM) (90% vs. 95%–98%) while reducing the running time by a factor of 190 and reducing the memory requirement by a factor of 104. Per minute EE estimation using activity-specific models resulted in an accurate EE prediction (RMSE of 0.53 METs vs. RMSE of 0.69 METs using previously reported SVM-branched models). These results demonstrate successful implementation of real-time physical activity monitoring and EE prediction system on a wearable platform.