Abstract We present a search for the lepton-flavor-violating decays B s 0 $$ {B}_s^0 $$ → ℓ ∓ τ ± , where ℓ = e, μ, using the full data sample of 121 fb −1 collected at the Υ(5S) resonance with the Belle detector at the KEKB asymmetric-energy e + e − collider. We use B s 0 B ¯ s 0 $$ {B}_s^0{\overline{B}}_s^0 $$ events in which one B s 0 $$ {B}_s^0 $$ meson is reconstructed in a semileptonic decay mode and the other in the signal mode. We find no evidence for B s 0 $$ {B}_s^0 $$ → ℓ ∓ τ ± decays and set upper limits on their branching fractions at 90% confidence level as B $$ \mathcal{B} $$ ( B s 0 $$ {B}_s^0 $$ → e ∓ τ ± ) < 14 × 10 −4 and B $$ \mathcal{B} $$ ( B s 0 $$ {B}_s^0 $$ → μ ∓ τ ± ) < 7.3 × 10 −4. Our result represents the first upper limit on the B s 0 $$ {B}_s^0 $$ → e ∓ τ ± decay rate.