The current research was carried out to determine the associations between the rumen microbiota and traits related with feed efficiency in a Holstein cattle population (n = 30) using whole metagenome sequencing. Improving feed efficiency (FE) is important for a more sustainable livestock production. The variability for the efficiency of feed utilization in ruminants is partially controlled by the gastrointestinal microbiota. Modulating the microbiota composition can promote a more sustainable and efficient livestock. This study revealed that most efficient cows had larger relative abundance of Bacteroidetes (P = 0.041) and Prevotella (P = 0.003), while lower, but non-significant (P = 0.119), relative abundance of Firmicutes. Methanobacteria (P = 0.004) and Methanobrevibacter (P = 0.003) were also less abundant in the high-efficiency cows. A de novo metagenome assembly was carried out using de Bruijn graphs in MEGAHIT resulting in 496,375 contigs. An agnostic pre-selection of microbial contigs allowed high classification accuracy for FE and intake levels using hierarchical classification. These microbial contigs were also able to predict FE and intake levels with accuracy of 0.19 and 0.39, respectively, in an independent population (n = 31). Nonetheless, a larger potential accuracy up to 0.69 was foreseen in this study for datasets that allowed a larger statistical power. Enrichment analyses showed that genes within these contigs were mainly involved in fatty acids and cellulose degradation pathways. The findings indicated that there are differences between the microbiota compositions of high and low-efficiency animals both at the taxonomical and gene levels. These differences are even more evident in terms of intake levels. Some of these differences remain even between populations under different diets and environments, and can provide information on the feed utilization performance without information on the individual intake level.