MicroRNAs (miRNAs) represent a second regulatory network that has important effects on gene expression and protein translation during biological process. However, the possible role of miRNAs in the early stages of fish sex differentiation is not well understood. In this study, we carried an integrated analysis of miRNA and mRNA expression profiles to explore their possibly regulatory patterns at the critical stage of sex differentiation in tilapia. We identified 279 pre-miRNA genes in tilapia genome, which were highly conserved in other fish species. Based on small RNA library sequencing, we identified 635 mature miRNAs in tilapia gonads, in which 62 and 49 miRNAs showed higher expression in XX and XY gonads, respectively. The predicted targets of these sex-biased miRNAs (e.g., miR-9, miR-21, miR-30a, miR-96, miR-200b, miR-212 and miR-7977) included genes encoding key enzymes in steroidogenic pathways (Cyp11a1, Hsd3b, Cyp19a1a, Hsd11b) and key molecules involved in vertebrate sex differentiation (Foxl2, Amh, Star1, Sf1, Dmrt1, and Gsdf). These genes also showed sex-biased expression in tilapia gonads at 5 dah. Some miRNAs (e.g., miR-96 and miR-737) targeted multiple genes involved in steroid synthesis, suggesting a complex miRNA regulatory network during early sex differentiation in this fish. The sequence and expression patterns of most miRNAs in tilapia are conserved in fishes, indicating the basic functions of vertebrate miRNAs might share a common evolutionary origin. This comprehensive analysis of miRNA and mRNA at the early stage of molecular sex differentiation in tilapia XX and XY gonads lead to the discovery of differentially expressed miRNAs and their putative targets, which will facilitate studies of the regulatory network of molecular sex determination and differentiation in fishes.