Introduction: Whether adjuvant therapy with aromatase inhibitors (AIs) causes sleep disturbances or not in postmenopausal women with early breast cancer (EBC) is still a controversial issue. Methods: Between March 2014 and November 2017, validated questionnaires for assessing insomnia, anxiety, depression, quality of life (QoL) and restless legs syndrome (RLS) were administered to 160 EBC patients at baseline and after 3, 6, 12, and 24 months of AI therapy. Results: AI therapy significantly decreased the patients’ QoL, but did not influence insomnia, anxiety or depression. However, it significantly increased the frequency and severity of RLS. Patients with RLS at baseline (19%) or who developed RLS during AI therapy (26.3%) reported statistically lower quality of sleep, higher anxiety and depression, and worse QoL compared to patients who never reported RLS (54.7%). Conclusion: Although AI therapy does not affect sleep quality, it may increase RLS frequency. The presence of RLS could identify a group of EBC patients who may benefit from psychological support.