Background: Previous research suggests that the processing of internal body sensations (interoception) affects how we experience pain. There is some evidence that people with fibromyalgia syndrome (FMS), which is a condition characterised by chronic pain and fatigue, may have altered interoceptive processing. However, extant findings are inconclusive, and some tasks previously used to measure interoception are of questionable validity. We used a task which overcomes problems with previous tasks – the Phase Adjustment Task (PAT) – to measure interoception in adults with FMS. Methods: We examined: (i) the tolerability of the PAT in an FMS sample (N = 154); (ii) if there are differences in facets of interoception (PAT performance, PAT-related confidence, and scores on the Private Body Consciousness Scale) between an FMS sample and an age- and gender-matched pain-free control sample (N = 94); and (iii) if subgroups of participants with FMS could be identified according to interoceptive accuracy levels. Results: After including additional task breaks and a recommended hand posture, we found that the PAT was tolerable in the FMS sample. Participants in the FMS sample were more likely to be classified as ‘interoceptive’ on the PAT, and had significantly higher self-reported interoception and interoceptive beliefs compared to participants in the pain-free sample. Within the FMS sample, participants who were classified as interoceptive on the PAT had significantly lower symptom impact than the unclassified participants. Conversely, self-reported interoception was positively correlated with FMS symptom severity and impact. Conclusions: The present findings suggest that interoception may be an important factor to consider in understanding and managing FMS symptoms, and that the PAT is a useful tool for assessing interoception in this population. We recommend future longitudinal work to better understand associations between fluctuating FMS symptoms and interoceptive processing.