MicroRNAs (miRNAs) play an important role in guiding development and maintaining function of the human heart. Dysregulation of miRNAs has been linked to various congenital heart diseases including Tetralogy of Fallot (TOF), which represents the most common cyanotic heart malformation in humans. Several studies have identified dysregulated miRNAs in right ventricular (RV) tissues of TOF patients. In this study, we profiled genome-wide the whole transcriptome and analyzed the relationship of miRNAs and mRNAs of RV tissues of a homogeneous group of 22 non-syndromic TOF patients. Observed profiles were compared to profiles obtained from right and left ventricular tissue of normal hearts. To reduce the commonly observed large list of predicted target genes of dysregulated miRNAs, we applied a stringent target prediction pipeline integrating probabilities for miRNA-mRNA interaction. The final list of disease-related miRNA-mRNA pairs comprises novel as well as known miRNAs including miR-1 and miR-133, which are essential to cardiac development and function by regulating KCNJ2, FBN2, SLC38A3 and TNNI1. Overall, our study provides additional insights into post-transcriptional gene regulation of malformed hearts of TOF patients.