Cervical cancer is a leading severe malignancy throughout the world. Molecular processes and biomarkers leading to tumor progression in cervical cancer are either unknown or only partially understood. An increasing number of studies have shown that microRNAs play an important role in tumorigenesis so understanding the regulatory mechanism of miRNAs in gene-regulatory network will help elucidate the complex biological processes that occur during malignancy. Functional genomics data provides opportunities to study the aberrant microRNA-messenger RNA (miRNA-mRNA) interaction. Identification of miRNA-mRNA regulatory modules will aid deciphering aberrant transcriptional regulatory network in cervical cancer but is computationally challenging. In this regard, an algorithm, termed as relevant and functionally consistent miRNA-mRNA modules (RFCM3), is proposed. It integrates miRNA and mRNA expression data of cervical cancer for identification of potential miRNA-mRNA modules. It selects set of miRNA-mRNA modules by maximizing relation of mRNAs with miRNA and functional similarity between selected mRNAs. Later, using the knowledge of the miRNA-miRNA synergistic network different modules are fused and finally a set of modules are generated containing several miRNAs as well as mRNAs. This type of module explains the underlying biological pathways containing multiple miRNAs and mRNAs. The effectiveness of the proposed approach over other existing methods has been demonstrated on a miRNA and mRNA expression data of cervical cancer with respect to enrichment analyses and other standard metrices. The prognostic value of the genes in a module with respect to cervical cancer is also demonstrated. The approach was found to generate more robust, integrated, and functionally enriched miRNA-mRNA modules in cervical cancer. © 2004-2012 IEEE.