Dry-matter intake is costly to obtain and may not provide insight into mechanisms of feed efficiency. Our objectives were to evaluate feed digestibility via fecal sampling and determine associations with phenotypic and genetic merit of milk yield and composition. Fecal samples were obtained from 115 Holsteins cows in March 2012 with 48 resampled in August. Samples were dried, ground to 1 mm, and placed in Ankom filter bags to determine % neutral detergent fiber (NDF%) or % indigestible NDF (iNDF%) for morning (n = 32 in March; n = 48 in August), afternoon (n = 18; March), evening (n = 16; March), and composite (n = 86; March) sample periods. Sample disappearance following placement into a cannulated rumen for 12 d determined iNDF%. An Ankom A200 analyzer was used to determine fecal NDF%; TMR samples were evaluated using the same procedures. Total-tract DM digestibility (TTDM%) was calculated as 1 - (TMR iNDF%/Feces iNDF%); total-tract NDF digestibility (TTNDF%) was calculated as 1 – [(TMR iNDF% × Feces NDF%)/(Feces iNDF% × TMR NDF%)]. TTDM% and TTNDF% were merged with phenotypes and estimated breeding values for milk yield, fat yield and %, and protein yield and %. The average composite TTDM% and TTNDF% in March was 65.8% ± 2.4 and 42.9% ± 2.7, respectively. Correlations of TTNDF% among sample periods were significant (P < 0.05), ranging from 0.56 to 0.92; correlations among sample periods for TTDM% ranged from 0.30 (not significant) to 0.94. August TTDM% (59.3% ± 4.4) and TTNDF% (38.4% ± 4.0) were lower and August TTNDF% was significantly correlated with March morning (0.72). Significant and unfavorable correlations of TTNDF% with milk (−0.27) and protein (−0.30) yields were observed, whereas higher milk-fat % was positively correlated with TTDM% and TTNDF% (0.26 and 0.44, respectively). Likewise, genetic merit for higher milk (−0.34) and protein (−0.30) yield was unfavorably correlated with TTNDF%, and increased genetic merit for milk-fat % was associated with higher TTNDF% (0.39) and TTDM% (0.27). Fecal sampling could provide a cost effective indicator of feed efficiency and higher milk-fat % was associated with improved digestibility.