We generalize the concept of coherent states, traditionally defined as special families of vectors on Hilbert spaces, to Hilbert modules. We show that Hilbert modules over $C^*$-algebras are the natural settings for a generalization of coherent states defined on Hilbert spaces. We consider those Hilbert $C^*$-modules which have a natural left action from another $C^*$-algebra say, $mathcal A$. The coherent states are well defined in this case and they behave well with respect to the left action by $mathcal A$. Certain classical objects like the Cuntz algebra are related to specific examples of coherent states. Finally we show that coherent states on modules give rise to a completely positive kernel between two $C^*$-algebras, in complete analogy to the Hilbert space situation. Related to this there is a dilation result for positive operator valued measures, in the sense of Naimark. A number of examples are worked out to illustrate the theory.