The early diagnosis of melanoma is critical to achieving reduced mortality and increased survival. Although clinical examination is currently the method of choice for melanocytic lesion assessment, there is a growing interest among clinicians regarding the potential diagnostic utility of computerised image analysis. Recognising that there exist significant shortcomings in currently available algorithms, we are motivated to investigate the utility of lacunarity, a simple statistical measure previously used in geology and other fields for the analysis of fractal and multi-scaled images, in the automated assessment of melanocytic naevi and melanoma. Digitised dermoscopic images of 111 benign melanocytic naevi, 99 dysplastic naevi and 102 melanomas were obtained over the period 2003 to 2008, and subject to lacunarity analysis. We found the lacunarity algorithm could accurately distinguish melanoma from benign melanocytic naevi or non-melanoma without introducing many of the limitations associated with other previously reported diagnostic algorithms. Lacunarity analysis suggests an ordering of irregularity in melanocytic lesions, and we suggest the clinical application of this ordering may have utility in the naked-eye dermoscopic diagnosis of early melanoma.