Fibromyalgia is a complex disorder, and its diagnosis often comprises a challenge for physicians. We aimed to assess the time from the appearance of early symptoms to the definite diagnosis of fibromyalgia and to delineate patient and physician factors associated with this delay. The database of a large healthcare services provider was searched for all fibromyalgia patients (age 21 years or more) diagnosed during 2008-2011. Patients with a diagnosis confirmed by a physician with a relevant specialization were compared with age- and sex-matched nonfibromyalgia controls to retrospectively identify an initial complaint pattern characteristic of fibromyalgia. The time from initial complaints to fibromyalgia diagnosis, as well as the fraction of time while the patient was treated continuously by the same primary physician as at time of diagnosis, was assessed among all eligible fibromyalgia patients. An initial complaint pattern was identified in 67.9% of 2,055 patients with confirmed fibromyalgia vs. 27.6% of 9,172 controls. Among 2,369 (69.0%) of all 3,434 eligible patients with fibromyalgia, mean (SD) total time to diagnosis was 6.42 (3.57) years and mean (SD) time while treated by the same primary physician as at diagnosis was 3.75 (3.26) years. Comorbidity, younger patient, and older physician age were associated with longer time to diagnosis. By analysis of "real-world" data, fibromyalgia remains a complex and elusive diagnosis, taking years to be properly diagnosed. There is a need to increase the awareness of this syndrome among physicians, especially of older age.