We report the first observation of a baryonic $B_s^0$ decay, $B_s^0 to p kern 0.1emoverline{kern -0.1emLambda} 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.1emoverline{kern -0.1emLambda} 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.1emoverline{kern -0.1emLambda} 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$.