Olfactomedin 4 (OLFM4) is a member of the olfactomedin domain-containing olfactomedin glycoprotein family and plays important roles in innate immunity, inflammation, and cancer. It exhibits increased expression in gastric cancer patient tissues and has been shown to regulate proliferation and apoptosis in gastric cancer cells. However, the molecular mechanism(s) underlying OLFM4’s role in gastric cancer remain unknown. In this study, we found that OLFM4 knock-down significantly inhibited YCC3 gastric cancer cell proliferation and induced G2/M cell cycle arrest. Yeast two-hybridization screening revealed that OLFM4 directly interacts with cyclin B1 interacting protein 1 (CCNB1IP1), an E3 ubiquitin protein ligase. In YCC3 cells, OLFM4 co-immunoprecipitated and colocalized with CCNB1IP1, and underwent cell cycle phase-specific nucleo-cytoplasmic shuttling. OLFM4 knockdown decreased both cyclin B1 protein levels and CDK1 activity in YCC3 cells. Screening of a cohort of OLFM4-targeted microRNAs (miRNAs) for their impact on cell proliferation identified several that significantly downregulated OLFM4 protein levels and inhibited YCC3 cell proliferation in vitro. Rescue experiments demonstrated that these miRNAs’ inhibitory effect on cell proliferation was partially related to their downregulation of OLFM4. When three of these miRNAs were individually administered intratumorally to nude mice bearing YCC3 cell xenografts, tumor growth was significantly inhibited when compared with tumors treated with a negative control miRNA. These results suggest that OLFM4 promotes cell cycle progression and cell proliferation in gastric cancer cells and may have utility as a therapeutic target in gastric adenocarcinoma.