We introduce a new method to search for the lepton-flavor violating Higgs decays $h\to\tau\mu$ and $h\to\tau e$ in the leptonic $\tau$ decay channel. In particular, the Standard Model background is estimated in a fully data driven way. The method exploits the asymmetry between electrons and muons in the final state of signal events and is sensitive to differences in the rates of the two decays. Using this method, we investigate the LHC sensitivity to these processes. With 20 fb^{-1} of data at $\sqrt{s}=8$ TeV, we expect a $3\sigma$ sensitivity for observing branching ratios of order $0.9\%$. The method and the suggested statistical treatment are discussed in detail.