Rhabdomyosarcoma (RMS) in children occurs as two major histological subtypes, embryonal (ERMS) and alveolar (ARMS). ERMS is associated with an 11p15.5 loss of heterozygosity (LOH) and may be confused with nonmyogenic, non-RMS soft tissue sarcomas. ARMS expresses the product of a genomic translocation that fuses FOXO1 (FKHR) with either PAX3 or PAX7 (P-F); however, at least 25% of cases lack these translocations. Here, we describe a genomic-based classification scheme that is derived from the combined gene expression profiling and LOH analysis of 160 cases of RMS and non-RMS soft tissue sarcomas that is at variance with conventional histopathological schemes. We found that gene expression profiles and patterns of LOH of ARMS cases lacking P-F translocations are indistinguishable from conventional ERMS cases. A subset of tumors that has been histologically classified as RMS lack myogenic gene expression. However, classification based on gene expression is possible using as few as five genes with an estimated error rate of less than 5%. Using immunohistochemistry, we characterized two markers, HMGA2 and TFAP2ss, which facilitate the differential diagnoses of ERMS and P-F RMS, respectively, using clinical material. These objectively derived molecular classes are based solely on genomic analysis at the time of diagnosis and are highly reproducible. Adoption of these molecular criteria may offer a more clinically relevant diagnostic scheme, thus potentially improving patient management and therapeutic RMS outcomes.