Linkage of rumen microbial structure to host phenotypical traits may enhance the understanding of host-microbial interactions in livestock species. This study used culture-independent PCR-denaturing gradient gel electrophoresis (PCR-DGGE) to investigate the microbial profiles in the rumen of cattle differing in feed efficiency. The analysis of detectable bacterial PCR-DGGE profiles showed that the profiles generated from efficient steers clustered together and were clearly separated from those obtained from inefficient steers, indicating that specific bacterial groups may only inhabit in efficient steers. In addition, the bacterial profiles were more likely clustered within a certain breed, suggesting that host genetics may play an important role in rumen microbial structure. The correlations between the concentrations of volatile fatty acids and feed efficiency traits were also observed. Significantly higher concentrations of butyrate (P < 0.001) and valerate (P = 0.006) were detected in the efficient steers. Our results revealed potential associations between the detectable rumen microbiota and its fermentation parameters with the feed efficiency of cattle.