We present the first calculation of the two-loop electroweak fermionic correction to the flavour-dependent effective weak-mixing angle for bottom quarks, sin^2 theta_{eff}^{b anti-b}. For the evaluation of the missing two-loop vertex diagrams, two methods are employed, one based on a semi-numerical Bernstein-Tkachov algorithm and the second on asymptotic expansions in the large top-quark mass. A third method based on dispersion relations is used for checking the basic loop integrals. We find that for small Higgs-boson mass values, M_H ~ 100 GeV, the correction is sizable, of order O(10^{-4}).