Techniques are provided for machine learning-based prediction of message responses using a corpus of response templates. One method comprises obtaining a user message sent by a user; applying the user message to a machine learning model that predicts a response template, from a corpus of response templates, that is responsive to the user message, wherein the machine learning model is trained using training data comprising historical user messages sent by multiple users and agent messages sent by customer service agents, wherein the agent messages: (i) have a similarity score with respect to at least one of the response templates that satisfies one or more similarity criteria, and (ii) are sent in response to a corresponding historical user message; and automatically generating a response to the user message using the predicted response template.