Investigating patients' reports on the quality and consistency of melanoma follow-up care in Australia would assist in evaluating if this care is effective and meeting patients' needs. The objective of this study was to obtain and explore the patients' account of the technical and interpersonal aspects of melanoma follow-up care received. An online survey was conducted to acquire details of patients' experience. Participants were patients treated in Australia for primary melanoma. Qualitative and quantitative data about patient perceptions of the nature and quality of their follow-up care were collected, including provision of melanoma specific information, psychosocial support, and imaging tests received. Inconsistencies were reported in the provision and quality of care received. Patient satisfaction was generally low and provision of reassurance from health professionals was construed as an essential element of quality of care. "Gaps" in follow-up care for melanoma patients were identified, particularly provision of adequate psychosocial support and patient education. Focus on strategies for greater consistency in the provision of support, information, and investigations received, may generate a cost dividend which could be reinvested in preventive and supportive care and benefit patient well-being.