Bmi-1 and Mel-18 are structural homologues that belong to the Polycomb group of transcriptional regulators and are believed to stably maintain repression of gene expression by altering the state of chromatin at specific promoters. While a number of clinical and experimental observations have implicated Bmi-1 in human tumorigenesis, the role of Mel-18 in cancer cell growth has not been investigated. We report here that short hairpin RNA-mediated knockdown of either Bmi-1 or Mel-18 in human medulloblastoma DAOY cells results in the inhibition of proliferation, loss of clonogenic survival, anchorage-independent growth, and suppression of tumor formation in nude mice. Furthermore, overexpression of both Bmi-1 and Mel-18 significantly increases the clonogenic survival of Rat1 fibroblasts. In contrast, stable downregulation of Bmi-1 or Mel-18 alone does not affect the growth of normal human WI38 fibroblasts. Proteomics-based characterization of Bmi-1 and Mel-18 protein complexes isolated from cancer cells revealed substantial similarities in their respective compositions. Finally, gene expression analysis identified a number of cancer-relevant pathways that may be controlled by Bmi-1 and Mel-18 and also showed that these Polycomb proteins regulate a set of common gene targets. Taken together, these results suggest that Bmi-1 and Mel-18 may have overlapping functions in cancer cell growth.