Background: Complex post-traumatic stress disorder (CPTSD) is a severely debilitating recently added symptom cluster in the International Classification of Diseases (ICD-11). So far, only limited information on mental health treatment-uptake and -satisfaction of individuals with CPTSD is available. The aim of this study is to investigate these aspects in a representative sample of the German general population. Methods: Participants completed the International Trauma Questionnaire (ITQ) to identify participants with CPTSD, as well as questionnaires on mental health treatment uptake and satisfaction, adverse childhood experiences, anxiety, depression, working ability, personality functioning, and epistemic trust. Results: Of the included n = 1918 participants, n = 29 (1.5%) fulfilled the criteria for CPTSD. Participants with CPTSD had received mental health treatment significantly more often than participants with PTSD or depression (65.5% vs. 58.8% vs. 31.6%; p = 0.031) but reported significantly less symptom improvement (52.9% vs. 78.0% vs. 80.0%; p = 0.008). Lower levels of epistemic trust were associated with higher CPTSD symptoms (p < 0.001). Conclusions: Our study shows that while the vast majority of individuals with CPTSD had received mental health treatment, subjective symptom improvement rates are not satisfactory. CPTSD was associated with a broad number of comorbidities and impairments in functioning. Lower levels of epistemic trust may partially explain worse treatment outcomes.