Aberrant miRNA expression abnormally modulates gene expression in cells and can contribute to tumorigenesis in humans. This study identified functionally relevant differentially expressed genes using the transcription factors and miRNA-co-regulated network analysis for gastric cancer. The TF-miRNA co-regulatory network was constructed based on data obtained from cDNA microarray and miRNA expression profiling of gastric cancer tissues. The network along with their co-regulated genes was analyzed using Database for Annotation, Visualization and Integrated Discovery (DAVID) and Transcriptional Regulatory Element Database (TRED). We found eighteen (17 up-regulated and 1 down-regulated) differentially expressed genes that were co-regulated by transcription factors and miRNAs. KEGG pathway analysis revealed that these genes were part of the extracellular matrix-receptor interaction and focal adhesion signaling pathways. In addition, qRT- PCR and Western blot data showed an increase in COL1A1 and decrease in NCAM1 mRNA and protein levels in gastric cancer tissues. Thus, these data provided the first evidence to illustrate that altered gene network was associated with gastric cancer invasion. Further study with a large sample size and more functional experiments is needed to confirm these data and contribute to diagnostic and treatment strategies for gastric cancer.