Residual Feed Intake (RFI) is an economically relevant trait in beef cattle. Among the molecular regulatory mechanisms, microRNAs (miRNAs) are an important dimension in post-transcriptional regulation and have been associated with different biological pathways. Here, we performed differential miRNAs expression and weighted gene co-expression network analyses (WGCNA) to better understand the complex interactions between miRNAs and mRNAs expressed in bovine skeletal muscle and liver. MiRNA and mRNA expression data were obtained from Nelore steers that were genetically divergent for RFI (N = 10 [low RFI or feed efficient]; N = 10 [high RFI or feed inefficient]). Differentially expressed and hub miRNAs such as bta-miR-486, bta-miR-7, bta-miR15a, bta-miR-21, bta-miR 29, bta- miR-30b, bta-miR-106b, bta-miR-199a-3p, bta-miR-204, and bta-miR 296 may have a potential role in variation of RFI. Functional enrichment analysis of differentially expressed (DE) miRNA’s target genes and miRNA–mRNA correlated modules revealed that insulin, lipid, immune system, oxidative stress and muscle development signaling pathways might potentially be involved in RFI in this population. Our study identified DE miRNAs, miRNA - mRNA regulatory networks and hub miRNAs related to RFI. These findings suggest a possible role of miRNAs in regulation of RFI, providing new insights into the potential molecular mechanisms that control feed efficiency in Nelore cattle.