Protein Kinase (casein kinase 2, CK2) is a serine-threonine kinase that is frequently dysregulated in many human tumors. Therefore we hypothesized that peptides capable of binding to the CK2 acidic domain may exhibit potential anticancer properties. By screening a random cyclic peptide phage display library, we have identified a novel peptide, P15, that abrogated CK2 phosphorylation by blocking the substrate in vitro. To verify its potential antineoplastic effect, P15 was fused to the cell-penetrating peptide derived from the HIV-Tat protein. Interestingly, P15-Tat induced apoptosis as evidenced by rapid caspase activation and cellular cytotoxicity in a variety of tumor cell lines. Furthermore, direct injection of P15-Tat into C57BL6 mice bearing day 7-established solid tumors, resulted in substantial regression of the tumor mass. Our findings describe a new proapoptotic cyclic peptide that blocks the CK2 phosphorylation and exhibits antitumor effect in vivo, indicating that the P15 peptide may potentially be used clinically to treat solid tumors or as an adjuvant for cancer therapy.