We compute the branching fractions of B-s,B-d --> e(+)e(-) in the type-II two-Higgs-doublet model with large tan beta. We find that the parameters of the neutral Higgs sector of the two-Higgs-doublet model cancel in the result, so that the branching fractions depend only on the charged Higgs mass and tan beta. For large values of tan beta and a charged Higgs mass above the bound from b --> s gamma, we find that the branching fractions can be enhanced by up to an order of magnitude or suppressed by up to a factor of two compared to the Standard Model result. We point out that previous calculations in the literature are gauge-dependent due to the omission of an important diagram, which gives the dominant contribution in the 't Hooft-Feynman gauge. We have analyzed in detail the region of the (M-H+, tan beta) plane to be probed by searches for B-s --> mu(+)mu(-) in Run II of the Tevatron. Since the branching fraction increases like tan(4) beta, this decay mode is complementary to b --> s gamma and efficiently probes the large tan beta region. For tan beta = 60, an integrated luminosity of 20 fb(-1) in an extended Run II will probe charged Higgs masses up to 260 GeV, if the background to B-s --> mu(+)mu(-) is small. For the same value of tan beta, the LHC may be able to explore charged Higgs masses up to 1 TeV using this decay. (C) 2000 Elsevier Science B.V. All rights reserved.