Hydroxyurea has been shown to be efficacious for the treatment of sickle cell anemia (SCA), primarily through the induction of fetal hemoglobin (HbF). However, the exact mechanisms by which hydroxyurea can induce HbF remain incompletely defined, although direct transcriptional effects and altered cell cycle kinetics have been proposed. In this study, we investigated potential epigenetic and alternative molecular mechanisms of hydroxyurea-mediated HbF induction by examining methylation patterns within the (G)γ-globin promoter and miRNA expression within primary CD71(+) erythrocytes of patients with SCA, both at baseline before beginning hydroxyurea therapy and after reaching maximum tolerated dose (MTD). Using both cross-sectional analysis and paired-sample analysis, we found that the highly methylated (G)γ-globin promoter was inversely correlated to baseline HbF levels, but only slightly altered by hydroxyurea treatment. Conversely, expression of several specific miRNAs was significantly increased after hydroxyurea treatment, and expression of miR-26b and miR-151-3p were both associated with HbF levels at MTD. The significant associations identified in these studies suggest that methylation may be important for regulation of baseline HbF, but not after hydroxyurea treatment, whereas changes in miRNA expression may be associated with hydroxyurea-mediated HbF induction. This study was registered at ClinicalTrials.gov (NCT00305175).