The Mycobacterium bovis bacillus Calmette-Guérin cell-wall skeleton (BCG-CWS) activates Toll-like receptor (TLR) 2 and TLR4, but unlike the typical TLR4 agonist bacterial lipopolysaccharide barely induces type 1 IFN. BCG-CWS has been used for adjuvant immunotherapy for patients with cancer. We investigated the adjuvant potential of BCG-CWS for induction of CTLs subsequent to TLR-mediated dendritic cell (DC) maturation, using a syngeneic mouse tumor model (B16 melanoma in C57BL/6). We evaluated the retardation of tumor growth and cytotoxic response in wild-type and MyD88−/− mice immunized with tumor debris and/or BCG-CWS. Delays in tumor growth and cytotoxic response were induced by immunization with a mixture of BCG-CWS emulsion and the tumor. BCG-CWS was capable of activating DCs ex vivo by the criteria of CD80/CD86 up-regulation and cytokine (interleukin-12, tumor necrosis factor-α) induction. Efficient tumor suppression and ex vivo cytokine induction did not occur in MyD88-deficient mice and cells, suggesting that the MyD88 adapter is crucial for induction of tumor cytotoxicity. Because TLR4 is involved in both MyD88-dependent and -independent pathways and the latter affects DC maturation, our findings indicate that both pathways cooperate to induce CTL-based tumor immunity.