Soft-tissue sarcomas are group of rare, tremendously heterogeneous, and highly aggressive malignancies. Characterizing inter-tumor heterogeneity is crucial for selecting suitable sarcoma therapy, as the presence of diverse molecular subgroups of patients can be associated with disease outcome or response to treatment. While cancer subtypes are often characterized by differences in gene expression, the mechanisms that drive these differences are generally unknown. We therefore set out to model the regulatory mechanisms driving sarcoma heterogeneity. We subtyped soft-tissue sarcomas based on patient-specific, genome-wide gene regulatory networks and found pronounced regulatory heterogeneity in leiomyosarcoma—one of the most common soft-tissue sarcomas subtypes that arises in smooth muscle tissue. To characterize this regulatory heterogeneity, we developed a new computational framework. This method, PORCUPINE, combines knowledge on biological pathways with permutation-based network analysis to identify pathways that exhibit significant regulatory heterogeneity across a patient population. We applied PORCUPINE to patient-specific leiomyosarcoma networks modeled on data from The Cancer Genome Atlas and validated our results in an independent dataset from the German Cancer Research Center. PORCUPINE identified 37 heterogeneously regulated pathways, including pathways that represent potential targets for treatment of subgroups of leiomyosarcoma patients, such as FGFR and CTLA4 inhibitory signaling. We validated the detected regulatory heterogeneity through analysis of networks and chromatin states in leiomyosarcoma cell lines. In addition, we showed that the heterogeneity identified with PORCUPINE is not associated with methylation profiles or clinical features, thereby suggesting an independent mechanism of patient heterogeneity driven by the complex landscape of gene regulatory interactions.