Melanoma is the most deadly form of skin cancer and it is costly for dermatologists to screen every patient for melanoma. There is a need for a system to assess the risk of melanoma based on dermatological photographs of a skin lesion. However, the presence of illumination variation in the photographs can have a negative impact on lesion segmentation and classification performance. A novel multistage illumination modeling algorithm is proposed to correct the underlying illumination variation in skin lesion photographs. The first stage is to compute an initial estimate of the illumination map of the photograph using a Monte Carlo nonparametric modeling strategy. The second stage is to obtain a final estimate of the illumination map via a parametric modeling strategy, where the initial nonparametric estimate is used as a prior. Finally, the corrected photograph is obtained using the final illumination map estimate. The proposed algorithm shows better visual, segmentation, and classification results when compared to three other illumination correction algorithms, one of which is designed specifically for lesion analysis.