In this Letter, we describe a search for lepton flavor violation (LFV) in the bottomonium system. We search for leptonic decays Υ(nS)→μτ (n=1, 2, and 3) using the data collected with the CLEO III detector. We identify the τ lepton using its leptonic decay ντν̄ee and utilize multidimensional likelihood fitting with probability density function shapes measured from independent data samples. We report our estimates of 95% C.L. upper limits on LFV branching fractions of Υ mesons. We interpret our results in terms of the exclusion plot for the energy scale of a hypothetical new interaction versus its effective LFV coupling in the framework of effective field theory.