The first observation of the $B^0_s to D_s^{*mp} K^{pm}$ decay is reported using 3.0$fb^{-1}$ of proton-proton collision data collected by the LHCb experiment. The $D_s^{*mp}$ mesons are reconstructed through the decay chain $D_s^{*mp} to gamma D_s^{mp}(K^{mp}K^{pm}pi^{mp})$. The branching fraction relative to that for $B^0_s to D_s^{*-} pi^{+}$ is measured to be $0.068 pm 0.005 ^{+0.003}_{-0.002}$, where the first uncertainty is statistical and the second is systematic. Using a recent measurement of $BR(B^0_s to D_s^{*-} pi^{+})$ the absolute branching fraction of $B^0_s to D_s^{*mp} K^{pm}$ is measured as ( 16.3 $pm$ 1.2 (stat) $^{+0.7}_{-0.5}$ (syst) $pm$ 4.8 (norm) ) $times$ 10$^{-5}$, where the third uncertainty is due to the uncertainty on the branching fraction of the normalisation channel.