Mental health promotion programs are important in rural communities but the factors which influence program effectiveness remain unclear. The aim of this mixed-methods study was to assess how community resilience affected the implementation of a mental health promotion program in rural Tasmania, Australia. Four study communities were selected based on population size, rurality, access to local support services, history of suicide within the community, and maturity of the mental health promotion program. Data from self-report questionnaires (n = 245), including items of Communities Advancing Resilience Toolkit (CART) assessment, and qualitative (focus group and interview) data from key local stakeholders (n = 24), were pooled to explore the factors perceived to be influencing program implementation. Survey results indicate the primary community resilience strengths across the four sites were related to the ‘Connection and Caring’ domain. The primary community resilience challenges related to resources. Qualitative findings suggested lack of communication and leadership are key barriers to effective program delivery and identified a need to provide ongoing support for program staff. Assessment of perceived community resilience may be helpful in informing the implementation of mental health promotion programs in rural areas and, in turn, improve the likelihood of their success and sustainability.