A search is reported for heavy resonances decaying into eμ final states in proton-proton collisions recorded by the CMS experiment at the CERN LHC at s=13 TeV, corresponding to an integrated luminosity of 35.9 fb−1. The search focuses on resonance masses above 200 GeV. With no evidence found for physics beyond the standard model in the eμ mass spectrum, upper limits are set at 95% confidence level on the product of the cross section and branching fraction for this lepton-flavor violating signal. Based on these results, resonant τ sneutrino production in R-parity violating supersymmetric models is excluded for masses below 1.7 TeV, for couplings λ132 = λ231 = λ311′ = 0.01. Heavy Z′ gauge bosons with lepton-flavor violating transitions are excluded for masses up to 4.4 TeV. The eμ mass spectrum is also interpreted in terms of non-resonant contributions from quantum black-hole production in models with one to six extra spatial dimensions, and lower mass limits are found between 3.6 and 5.6 TeV. In all interpretations used in this analysis, the results of this search improve previous limits by about 1 TeV. These limits correspond to the most sensitive values obtained at colliders.[Figure not available: see fulltext.].