In this work, we propose to use pattern recognition methods to determine submaximal heart rate (HR) during specific contexts, such as walking at a certain speed, using wearable sensors in free living, and using context-specific HR to estimate cardiorespiratory fitness (CRF). CRF of 51 participants was assessed by a maximal exertion test (V̇o_{2 max}). Participants wore a combined accelerometer and HR monitor during a laboratory-based simulation of activities of daily living and for 2 wk in free living. Anthropometrics, HR while lying down, and walking at predefined speeds in laboratory settings were used to estimate CRF. Explained variance ( R²) was 0.64 for anthropometrics, and increased up to 0.74 for context-specific HR (0.73-0.78 when including fat-free mass). Next, we developed activity recognition and walking speed estimation algorithms to determine the same contexts (i.e., lying down and walking) in free living. Context-specific HR in free living was highly correlated with laboratory measurements (Pearson's r = 0.71–0.75). R²for CRF estimation was 0.65 when anthropometrics were used as predictors, and increased up to 0.77 when including free-living context-specific HR (i.e., HR while walking at 5.5 km/h). R²varied between 0.73 and 0.80 when including fat-free mass among the predictors. Root mean-square error was reduced from 354.7 to 281.0 ml/min by the inclusion of context-specific HR parameters (21% error reduction). We conclude that pattern recognition techniques can be used to contextualize HR in free living and estimated CRF with accuracy comparable to what can be obtained with laboratory measurements of HR response to walking.