A search for the direct production of Higgs bosons in the di-tau decay mode is performed with 86.3 +/- 3.5 pb(-1) of data collected with the Collider Detector at Fermilab during the 1994-1995 data taking period of the Tevatron. We search for events where one tau decays to an electron plus neutrinos and the other tau decays hadronically. We perform a counting experiment and set limits on the cross section for supersymmetric Higgs boson production where tan beta is large and m(A) is small. For a benchmark parameter space point where m(A)(0)=100 GeV/c(2) and tan beta=50, we limit the production cross section multiplied by the branching ratio to be less than 77.9 pb at the 95% confidence level compared to the theoretically predicted value of 11.0 pb. This is the first search for Higgs bosons decaying to tau pairs at a hadron collider.