Patients with chronic pain have complex pain profiles and associated problems. Subgroup analysis can help identify key problems. We used a data-based approach to define pain phenotypes and their most relevant associated problems in 320 patients undergoing tertiary pain management. Unsupervised machine learning analysis of parameters "pain intensity", "number of pain areas", "pain duration", "activity pain interference" and "affective pain interference", implemented as emergent self-organizing maps, identified three patient phenotype clusters. Supervised analyses, implemented as different types of decision rules, identified "affective pain interference" and the "number of pain areas" as most relevant for cluster assignment. These appeared 698 and 637 times, respectively, in 1000 cross-validation runs among the most relevant characteristics in an item categorization approach in a computed ABC analysis. Cluster assignment was achieved with a median balanced accuracy of 79.9%, a sensitivity of 74.1%, and a specificity of 87.7%. In addition, among 59 demographic, pain etiology, comorbidity, lifestyle, psychological, and treatment-related variables, sleep problems appeared 638 and 439 times among the most important characteristics in 1000 cross-validation runs where patients were assigned to the two extreme pain phenotype clusters. Also important were the parameters "fear of pain", "self-rated poor health", and "systolic blood pressure". Decision trees trained with this information assigned patients to the extreme pain-phenotype with an accuracy of 67%. Machine learning suggested sleep problems as key factors in the most difficult pain presentations, therefore deserving priority in the treatment of chronic pain.