Skin Cancer (SC) is among the most hazardous due to its high mortality rate. Therefore, early detection of this disease would be very helpful in the treatment process. Multilevel Thresholding (MLT) is widely used for extracting regions of interest from medical images. Therefore, this paper utilizes the recent Coronavirus Disease Optimization Algorithm (COVIDOA) to address the MLT issue of SC images utilizing the hybridization of Otsu, Kapur, and Tsallis as fitness functions. Various SC images are utilized to validate the performance of the proposed algorithm. The proposed algorithm is compared to the following five meta-heuristic algorithms: Arithmetic Optimization Algorithm (AOA), Sine Cosine Algorithm (SCA), Reptile Search Algorithm (RSA), Flower Pollination Algorithm (FPA), Seagull Optimization Algorithm (SOA), and Artificial Gorilla Troops Optimizer (GTO) to prove its superiority. The performance of all algorithms is evaluated using a variety of measures, such as Mean Square Error (MSE), Peak Signal-To-Noise Ratio (PSNR), Feature Similarity Index Metric (FSIM), and Normalized Correlation Coefficient (NCC). The results of the experiments prove that the proposed algorithm surpasses several competing algorithms in terms of MSE, PSNR, FSIM, and NCC segmentation metrics and successfully solves the segmentation issue.