The element $|V_{cb}|$ of the Cabibbo-Kobayashi-Maskawa matrix is measured using semileptonic $B_s^0$ decays produced in proton-proton collision data collected with the LHCb detector at center-of-mass energies of 7 and 8 TeV, corresponding to an integrated luminosity of 3 fb$^{-1}$. Rates of $B_s^0 \to D_s^{-} \mu^+ \nu_{\mu}$ and $B_s^0 \to D_s^{*-} \mu^+ \nu_{\mu}$ decays are analyzed using hadronic form-factor parametrizations derived either by Caprini, Lellouch and Neubert (CLN) or by Boyd, Grinstein and Lebed (BGL). The measured values of $|V_{cb}|$ are ${(41.4 \pm 0.6 \pm 0.9 \pm 1.2)\times 10^{-3}}$ and ${(42.3 \pm 0.8 \pm 0.9 \pm 1.2)\times 10^{-3}}$ in the CLN and BGL parametrization, respectively. The first uncertainty is statistical, the second systematic, and the third is due to the external inputs used in the measurement. These results are in agreement with those obtained from decays of $B^+$ and $B^0$ mesons. They are the first determinations of $|V_{cb}|$ at a hadron-collider experiment and the first using $B_s^0$ meson decays.