Active drug delivery by tumor-targeting peptides is a promising approach to improve existing therapies for rhabdomyosarcoma (RMS), by increasing the therapeutic effect and decreasing the systemic toxicity, e.g., by drug-loaded peptide-targeted nanoparticles. Here, we tested 20 different tumor-targeting peptides for their ability to bind to two RMS cell lines, Rh30 and RD, using quantum dots Streptavidin and biotin-peptides conjugates as a model for nanoparticles. Four peptides revealed a very strong binding to RMS cells: NCAM-1-targeting NTP peptide, nucleolin-targeting F3 peptide, and two Furin-targeting peptides, TmR and shTmR. F3 peptide showed the strongest binding to all RMS cell lines tested, low binding to normal control myoblasts and fibroblasts, and efficient internalization into RMS cells demonstrated by the cytoplasmic delivery of the Saporin toxin. The expression of the nucleophosphoprotein nucleolin, the target of F3, on the surface of RMS cell lines was validated by competition with the natural ligand lactoferrin, by colocalization with the nucleolin-binding aptamer AS1411, and by the marked sensitivity of RMS cell lines to the growth inhibitory nucleolin-binding N6L pseudopeptide. Taken together, our results indicate that nucleolin-targeting by F3 peptide represents a potential therapeutic approach for RMS.