Neutrino-induced charged-current coherent kaon production νμA→μ-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 the 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+, μ-, 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 3σ significance.