Residual feed intake (RFI) is a moderately heritable trait of feed efficiency in dairy cows. The main objective of the present study was to assess potential differences in the ruminal microbiome, milk fatty acid (FA) composition, and plasma concentrations of glucose, nonesterified fatty acids (NEFA), and β-hydroxybutyrate between the most (M-EFF) and the least efficient (L-EFF) dairy cows during early lactation. Forty-seven multiparous Holstein dairy cows with daily ad libitum access to a total mixed ration from 30 d before calving to 30 d in milk were used. Cows were retrospectively classified into M-EFF (i.e., low RFI, n = 29) and L-EFF (high RFI, n = 18) based on a linear regression model. Ruminal digesta and milk samples were collected from each cow at 15 and 30 d in milk for microbiome analysis using 16S rRNA gene sequencing. Microbiome sequencing data were analyzed with the QIIME 2 platform  (http://qiime.org/), whereas the microbiome statistical analyses and visual explorations were performed using the web-based MicrobiomeAnalyst platform. Milk FA composition was measured via gas chromatography-mass spectrometry. The statistical model used in SAS 9.4 (SAS Institute Inc.) included RFI, time, and their interactions as fixed effects. The cor() function in R programming was used to determine Pearson correlations between relative abundance of significant bacteria and milk FA. Overall, daily milk yield did not differ due to RFI and averaged 42 ± 1.6 kg for L-EFF and 43 ± 1.3 kg for M-EFF cows. However, M-EFF cows had lower overall dry matter intake (14.9 ± 0.5 kg/d) compared with L-EFF cows (19.2 ± 0.6 kg/d). No incidence of clinical disease was recorded for cows in the study. Compared with L-EFF, overall glucose concentration was lower, whereas NEFA and β-hydroxybutyrate concentrations were greater in M-EFF cows. Ruminal digesta from both RFI groups had similar bacterial composition, but differed in the relative abundance of some bacteria. Compared with L-EFF, M-EFF cows had greater relative abundance of Lachnospiraceae, Lachnoclostridium, Papillibacter, Desulfovibrio, Sphaerochaeta, Acetobacter, and Histophilus. In contrast, relative abundance of Bifidobacterium, Ruminiclostridium, Prevotellaceae, and Erysipelotrichaceae bacterium was lower in M-EFF cows. Compared with L-EFF, M-EFF cows had greater proportions of long-chain monounsaturated FA, including 16:1 trans-9, 16:1 cis-9, 17:1 trans-10, 17:1 cis-10, 18:1 cis-9, 18:1 cis-11, whereas proportions of medium-chain saturated and 16:0 were lower in M-EFF. Acetate-producing bacteria (Sphaerochaeta and Acetobacter) were positively and significantly correlated (r ≥ 0.24) with concentrations of 16:1 cis-9 and 17:1 cis-10, whereas Prevotellaceae was significantly and negatively correlated (r = −0.25) with these FA. Butyrate-producing bacterium (Papillibacter) had a significant negative correlation (r =−0.27) with concentration of 15:0. Overall, data suggested that feed-efficient cows have unique profiles of ruminal microbiota, some of which are correlated with concentrations of milk FA during early lactation.