The Wnt/β-catenin signaling pathway dominates numerous cellular processes including cell proliferation, differentiation, and epithelial-mesenchymal transition, which play a crucial role in human cancer malignancies. Regulator of G-protein signaling 3 (RGS3) is a pivotal molecule involved in the Wnt/β-catenin signaling pathway, which is worthy of intensive research as a potential target in cancer treatment. In this study, we found that RGS3 is significantly upregulated in gastric cancer (GC) tumor samples compared with normal samples from the analysis of two independent GC mRNA microarray datasets in the NCBI public database. Further immunohistochemistry assay and western-blot experiments confirmed this finding on the basis of the results of our own 102 paired GC specimens and three GC cell lines. We found that a high expression of RGS3 is associated with advanced TNM stages and more aggressive malignant behaviors. In addition, the association of overexpression of RGS3 and poor overall survival and progression-free survival outcomes suggests that RGS3 has the potential to serve as a molecular therapy target for GC. Interestingly, our pathways analysis and the follow-up dual-luciferase reporter assay showed that there is a direct 3'-untranslated region binding site between RGS3 mRNA and microRNA-126, a GC inhibitor. On the basis of all the above evidences, our findings suggest that overexpressed RGS3 regulated by microRNA-126 through the post-transcriptional modulation is associated significantly with a poor prognosis of GC patients.