We have searched for the lepton-flavor-violating decay B-0 -> K-*0 mu(+/-)e(-/+) using a data sample of 711 fb(-1) that contains 772 x 10(6) B (B) over bar pairs. The data were collected near the Upsilon(4S) resonance with the Belle detector at the KEKB asymmetric-energy e(+) e(-) collider. No signals were observed, and we set 90% confidence level upper limits on the branching fractions of B(B-0 -> K-*0 mu(+)e(-)) < 1.2 x 10(-7), B(B-0 -> K-*0 mu(-)e(+)) < 1.6 x 10(-7), and, for both decays combined, B(B-0 -> K-*0 mu(+/-)e(-/+)) < 1.8 x 10(-7). These are the most stringent limits on these decays to date.