Brain-Derived Neurotrophic Factor (BDNF) and its rs6265 single nucleotide polymorphism (SNP) play an important role in post-stroke recovery. We investigated the correlation between BDNF rs6265 SNP and recovery outcome, measured by the modified Barthel index, in 49 patients with stroke hospitalized in our rehabilitation center at baseline (T0) and after 30 sessions of rehabilitation treatment (T1); moreover, we analyzed the methylation level of the CpG site created or abolished into BDNF rs6265 SNP. In total, 11 patients (22.4%) were heterozygous GA, and 32 (65.3%) and 6 (12.2%) patients were homozygous GG and AA, respectively. The univariate analysis showed a significant relationship between the BDNF rs6265 SNP and the modified Barthel index cut-off (χ2(1, N = 48) = 3.86, p = 0.049), considering patients divided for carrying (A+) or not carrying (A−) the A allele. A higher percentage of A− patients obtained a favorable outcome, as showed by the logistic regression model corrected by age and time since the stroke onset, compared with the A+ patients (OR: 5.59). At baseline (T0), the percentage of BDNF methylation was significantly different between GG (44.6 ± 1.1%), GA (39.5 ± 2.8%) and AA (28.5 ± 1.7%) alleles (p < 0.001). After rehabilitation (T1), only patients A− showed a significant increase in methylation percentages (mean change = 1.3, CI: 0.4–2.2, p = 0.007). This preliminary study deserves more investigation to confirm if BDNF rs6265 SNP and its methylation could be used as a biological marker of recovery in patients with stroke undergoing rehabilitation treatment.