The first observation of the suppressed semileptonic $B_s^0 \to K^-\mu^+\nu_\mu$ decay is reported. Using a data sample recorded in {\it pp} collisions in 2012 with the LHCb detector, corresponding to an integrated luminosity of 2 $\mathrm{fb}^{-1}$, the branching fraction \mbox{$\mathcal{B}(B_s^0 \to K^-\mu^+\nu_\mu)$} is measured to be $(1.06\pm0.05~(\mathrm{stat})\pm0.08~(\mathrm{syst}))\times 10^{-4}$, where the first uncertainty is statistical and the second one represents the combined systematic uncertainties. The decay $B_s^0 \to D_s^-\mu^+\nu_\mu$, where $D_s^-$ is reconstructed in the final state $K^+K^-\pi^-$, is used as a normalization channel to minimize the experimental systematic uncertainty. Theoretical calculations on the form factors of the $B_s^0 \to K^-$ and $B_s^0 \to D_s^-$ transitions are employed to determine the ratio of the CKM matrix elements ${|V_{ub}|}/{|V_{cb}|}$ at low and high $B_s^0 \to K^-$ momentum transfer.