Background: Post-treatment follow-up for patients with American Joint Committee on Cancer (AJCC) stage I/II melanoma is believed to be important for early detection of disease recurrence and new primary melanomas, but comes with costs to both patients and healthcare providers. We aimed to determine how frequently a cohort of patients attended follow-up after surgical treatment at one Specialist Center. Methods: We used prospectively collected data from the Melanoma Institute Australia (MIA) for patients with AJCC stage I/II melanoma diagnosed between January 2008 and December 2011. The distribution of the number of recorded follow-up visits per patient was analyzed and compared with the number of follow-up visits recommended in the 2008 Australian and New Zealand Melanoma Management Guidelines. Results: A total of 3813 patients with stage I/II melanoma were identified. During the first year of follow-up post-surgery, 34 % of stage I patients and 14 % of stage II patients had the number of follow-up visits recommended in the guidelines. A large proportion of melanoma patients did not appear to be routinely followed up at MIA, with 43.2 % of stage I patients and 28.7 % of stage II patients having either no visit or only one visit post-surgery. During all years of follow-up, 13.2 % of stage I patients and 4.1 % of stage II patients had the number of follow-up visits at the specialist center as recommended in the guidelines. Conclusions: The large proportion of patients who had fewer follow-up visits than expected suggests (i) many patients are followed up in clinics elsewhere, and/or (ii) post-surgical surveillance is less frequent in practice.