Genetic improvement of feed efficiency in dairy cattle through direct selection is a challenge because of costs associated with measuring feed intake on individual cows. The identification of an easy to measure indicator trait of feed efficiency would help alleviate this problem. The objective of this study was to characterize the genetic variability and determine the relationship between surface body temperature and internal body temperature with feed efficiency in mid-lactation Holstein cows. Feed efficiency was measured as residual feed intake (RFI), defined as the difference between the actual intake and predicted intake based on milk energy, body weight change, and maintenance requirements. Individual daily feed intakes and milk production were recorded for 8 weeks on 124 primiparous cows between 50 and 200 d in milk. Weekly body weight and milk component data were also collected, and average RFI throughout the measurement period was calculated. Surface body temperature was measured weekly by thermal images taken of the lower right rear leg using a Fluke hand-held Thermal Imaging Scanner. The mean temperature in a defined region on the image was averaged across days for each cow. Rectal body temperatures were taken on imaging days and averaged for each cow. The ability of the body temperatures to explain variation in RFI was analyzed with a linear model, which included the fixed effect of replicate along with body temperature (surface or rectal) as a covariate. Heritabilities for body temperatures were estimated in ASReml. Rectal temperature did not significantly explain variation in RFI while surface leg temperature accounted for 2.8% of the total variance in RFI (P < 0.10). Average leg surface temperatures for the top and bottom quartiles for RFI were 25.3 and 24.9 C (SE 0.3) for high and low RFI, respectively. Rectal temperatures did not differ between high and low RFI quartiles. Leg surface temperature was moderately heritable (0.32 ± 0.32) while the heritability estimate of rectal temperature was 0.16 ± 0.26. This research demonstrates surface leg temperature is a heritable trait that explains a small portion of variation in RFI.