The first search in ppbar collisions at sqrt(s)=1.96 GeV for the production of neutral Higgs bosons in association with bottom quarks and decaying in two tau leptons is presented. The cross section for this process is enhanced in many extensions of the Standard Model (SM), such as its minimal supersymmetric extension (MSSM) at large tan(beta). The data, corresponding to an integrated luminosity of 328 pb-1, were collected with the D0 detector at the Fermilab Tevatron Collider. An upper limit is set on the production cross section of neutral Higgs bosons in the mass range of 90 to 150 GeV, and this limit is used to exclude part of the MSSM parameter space.