Neutrino-induced charged-current coherent kaon production, $ u_{mu}Arightarrowmu^{-}K^{+}A$, is a rare, inelastic electroweak process that brings a $K^+$ on shell and leaves the target nucleus intact in its ground state. This process is significantly lower in rate than neutrino-induced charged-current coherent pion production, because of Cabibbo suppression and a kinematic suppression due to the larger kaon mass. We search for such events in the scintillator tracker of MINERvA by observing the final state $K^+$, $mu^-$ and no other detector activity, and by using the kinematics of the final state particles to reconstruct the small momentum transfer to the nucleus, which is a model-independent characteristic of coherent scattering. We find the first experimental evidence for the process at $3sigma$ significance.