We present the results of a search for anomalous resonant production of tau lepton pairs with large invariant mass, the first such search using the CDF II Detector in Run II of the Tevatron pp collider. Such anomalous production could arise from various new physics processes. In a data sample corresponding to 195 pb(-1) of integrated luminosity we predict 2.8+/-0.5 events from standard model background processes and observe 4. We use this result to set limits on the production of heavy scalar and vector particles decaying to tau lepton pairs.