Toll-like receptor ligands are potentially useful adjuvants for the development of clinical T cell vaccination. Here we investigated the novel Toll-like receptor2 ligand P40, the outer membrane protein A derived from Klebsiella pneumoniae. Seventeen human leukocyte antigen-A*0201 positive stage III/IV melanoma patients were vaccinated with P40 and Melan-A/Mart-1 peptide subcutaneously in monthly intervals. Adverse reactions were mild-to-moderate. Fourteen patients received at least 8 vaccinations and were thus evaluable for clinical tumor and immune responses. Seven patients experienced progressive disease, whereas 2 patients had stable disease throughout the trial period, 1 of them with regression of multiple skin metastases. The remaining 5 patients had no measurable disease. Melan-A/Mart-1 specific CD8 T cells were analyzed ex vivo, with positive results in 6 of 14 evaluable patients. Increased percentages of T cells were found in three patients, memory/effector T cell differentiation in 4 patients, and a positive interferon-gamma Elispot assay in 1 patient. Antibody responses to P40 were observed in all patients. We conclude that vaccination with peptide and P40 was feasible and induced ex vivo detectable tumor antigen specific T cell responses in 6 of 14 patients with advanced melanoma.