This preliminary study investigates feasibility of a running speed based heart rate (HR) prediction. It is basically motivated from the assumption that there is a significant relationship between HR and the running speed. In order to verify the assumption, HR and running speed data from 217 subjects of varying aerobic capabilities were simultaneously collected during an incremental treadmill exercise. A running speed was defined as a treadmill speed and its corresponding heart rate was calculated by averaging the last one minute HR values of each session. The feasibility was investigated by assessing a correlation between the heart rate and the running speed using inter-subject (between-subject) and intra-subject (within-subject) datasets with regression orders of 1, 2, 3, and 4, respectively. Furthermore, HR differences between actual and predicted HRs were also employed to investigate the feasibility of the running speed in predicting heart rate. In the inter-subject analysis, a strong positive correlation and a reasonable HR difference (r = 0.866, 16.55 +/- 11.24 bpm @ 1st order; r = 0.871, 15.93 +/- 11.49 bpm @ 2nd order; r = 0.897, 13.98 +/- 10.80 bpm @ 3rd order; and r = 0.899, 13.93 +/- 10.64 bpm @ 4th order) were obtained, and a very high positive correlation and a very low HR difference (r = 0.978, 6.46 +/- 3.89 bpm @ 1st order; r = 0.987, 5.14 +/- 2.87 bpm @ 2nd order; r = 0.996, 2.61 +/- 2.03 bpm @ 3rd order; and r = 0.997, 2.04 +/- 1.73 bpm @ 4th order) were obtained in the intra-subject analysis. It can therefore be concluded that 1) heart rate is highly correlated with a running speed; 2) heart rate can be approximately estimated by a running speed with a proper statistical model (e.g., 3rd-order regression); and 3) an individual HR-speed calibration process may improve the prediction accuracy.