Background: The combination of first-year placements, an increasing proportion of mental health callouts, and the high incidence of mental illness in health-professional tertiary students means standard curricula may not adequately prepare early-year paramedic students for mental health challenges. Methods: A retrospective online survey was used to explore the experiences of paramedic students who have completed Mental Health First Aid (MHFA) training within their undergraduate studies. The content-validated survey explored the relevance, appropriateness, and novelty of MHFA training, and invited participants to reflect on the course strengths and weaknesses. Results: The majority of 102 respondents, predominantly female first- and second-year paramedic students aged 18–24 years, agreed the content was relevant (86%) and appropriate (88%), with 73% agreeing they would recommend to other university students. Thematic analysis identified strengths of the course as perceived increases in mental health literacy and empowerment to act on mental health concerns. A weakness was students perceived the course did not prepare them adequately for clinical practice. Conclusion: The inclusion of MHFA early in paramedic curricula is appropriate and relevant, increasing mental health literacy and empowering students to recognise and act upon mental health concerns. Application of practical scenarios may further enhance student learning experiences.