Cell replication integrates aberrations of cell cycle regulation and diverse upstream pathways which all can contribute to melanoma development and progression. In this study, cell cycle regulatory proteins were detected in situ in benign and malignant melanocytic tumors to allow correlation of major cell cycle fractions (G1, S-G2, and G2-M) with melanoma evolution. Dysplastic nevi expressed early cell cycle markers (cyclin D1 and cyclin-dependent kinase 2; Cdk2) significantly more (p < 0.05) than common nevi. Post-G1 phase markers such as cyclin A, geminin, topoisomerase IIα (peaking at S-G2) and aurora kinase B (peaking at G2-M) were expressed in thin (≤1 mm) melanomas but not in dysplastic nevi, suggesting that dysplastic melanocytes engaged in the cell cycle do not complete replication and remain arrested in G1 phase. In malignant melanomas, the expression of general and post-G1 phase markers correlated well with each other implying negligible cell cycle arrest. Post-G1 phase markers and Ki67 but none of the early markers cyclin D1, Cdk2 or minichromosome maintenance protein 6 (Mcm6) were expressed significantly more often in thick (>1 mm) than in thin melanomas. Marker expression did not differ between metastatic melanomas and thick melanomas, with the exception of aurora kinase A of which the expression was higher in metastatic melanomas. Combined detection of cyclin A (post-G1 phase) with Mcm6 (replication licensing) and Ki67 correctly classified thin melanomas and dysplastic nevi in 95.9 % of the original samples and in 93.2 % of cross-validated grouped cases at 89.5 % sensitivity and 92.6 % specificity. Therefore, cell cycle phase marker detection can indicate malignancy in early melanocytic lesions and accelerated cell cycle progression during vertical melanoma growth.