We report the first observation of a baryonic $B_s^0$ decay, $B_s^0 \to p \kern 0.1em\overline{\kern -0.1em\Lambda} K^-$, using proton-proton collision data recorded by the LHCb experiment at center-of-mass energies of 7 and 8 TeV, corresponding to an integrated luminosity of $3.0\,\mathrm{fb}^{-1}$. The branching fraction is measured to be $ \mathcal{B}(B_s^0 \to p \kern 0.1em\overline{\kern -0.1em\Lambda} K^-) + \mathcal{B}(B_s^0 \to \bar{p} \Lambda K^+) = \left[5.46 \pm 0.61 \pm 0.57 \pm 0.50 (\mathcal{B}) \pm 0.32 (f_s/f_d)\right]\times 10^{-6}, $ where the first uncertainty is statistical and the second systematic, the third uncertainty accounts for the experimental uncertainty on the branching fraction of the $B^0 \to p \kern 0.1em\overline{\kern -0.1em\Lambda} \pi^-$ decay used for normalization, and the fourth uncertainty relates to the knowledge of the ratio of $b$-quark hadronization probabilities $f_s/f_d$.