Uterine leiomyosarcomas (ULMSs) are aggressive smooth muscle tumors associated with poor clinical outcome. Despite previous cytogenetic and molecular studies, their molecular background has remained elusive. To examine somatic variation in ULMS, we performed exome sequencing on 19 tumors. Altogether, 43 genes were mutated in at least two ULMSs. Most frequently mutated genes included tumor protein P53 (TP53; 6/19; 33%), alpha thalassemia/mental retardation syndrome X-linked (ATRX; 5/19; 26%), and mediator complex subunit 12 (MED12; 4/19; 21%). Unlike ATRX mutations, both TP53 and MED12 alterations have repeatedly been associated with ULMSs. All the observed ATRX alterations were either nonsense or frameshift mutations. ATRX protein levels were reliably analyzed by immunohistochemistry in altogether 44 ULMSs, and the majority of tumors (23/44; 52%) showed clearly reduced expression. Loss of ATRX expression has been associated with alternative lengthening of telomeres (ALT), and thus the telomere length was analyzed with telomere-specific fluorescence in situ hybridization. The ALT phenotype was confirmed in all ULMSs showing diminished ATRX expression. Exome data also revealed one nonsense mutation in death-domain associated protein (DAXX), another gene previously associated with ALT, and the tumor showed ALT positivity. In conclusion, exome sequencing revealed that TP53, ATRX, and MED12 are frequently mutated in ULMSs. ALT phenotype was commonly seen in tumors, indicating that ATR inhibitors, which were recently suggested as possible new drugs for ATRX-deficient tumors, could provide a potential novel therapeutic option for ULMS.