Surgical excision is important for melanoma treatment. Delays in surgical excision after diagnosis of melanoma have been linked to decreased survival in hospital-based cohorts. This study was aimed at quantifying the association between the timeliness of surgical excision and overall survival in patients diagnosed with melanoma in hospital- and non-hospital-based settings, using a retrospective cohort study of patients with stage 0–III melanoma and using data linked between the North Carolina Central Cancer Registry to Medicare, Medicaid, and private health insurance plan claims across the state. We identified 6,496 patients diagnosed between 2004 and 2012 with follow-up through 2017. We categorized the time from diagnostic biopsy to surgical excision as < 6 weeks after diagnosis, 6 weeks to 90 days after diagnosis, and > 90 days after melanoma diagnosis. Multivariable Cox regression was used to estimate differences in survival probabilities. Five-year overall survival was lower for those with time to surgery over 90 days (78.6%) compared with those with less than 6 weeks (86%). This difference appeared greater for patients with Stage 1 melanoma. This study was retrospective, included one state, and could not assess melanoma specific mortality. Surgical timeliness may have an effect on overall survival in patients with melanoma. Timely surgery should be encouraged. Electronic supplementary material The online version of this article (10.1007/s00403-020-02146-2) contains supplementary material, which is available to authorized users.