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β is large and mA is small. For a benchmark parameter space point where mA0=100  GeV/c2 and tanβ=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.