Computerized analysis of skin lesions is an important issue in information retrieval for medical imaging, as it helps human specialists to improve their decision-making for prompt and accurate diagnosis of melanoma and other skin diseases. A relevant task in this regard is border detection, which gives valuable information about some clinical features of skin lesions. This task is typically carried out manually by the dermatologists, leading to errors inherent to subjective diagnosis. In this paper, we address this problem by applying a modification of a powerful evolutionary computation method, the firefly algorithm. The modified algorithm is hybridized with a local search procedure for better performance. Experimental results on a benchmark of medical images of skin lesions show that this method outperforms classical mathematical methods for the instances in the benchmark and is very competitive and often superior to state-of-the-art techniques in the field in terms of numerical accuracy. We conclude that the approach is very promising and can be useful in real-world medical applications where speed is not a critical factor.