Deep learning models such as Convolutional Neural Networks (CNNs) have shown the potential to classify medical images for accurate diagnosis. These techniques will face regulatory compliance challenges related to privacy of user data, especially when they are deployed as a service on a cloud platform. Fully Homomorphic Encryption (FHE) can enable CNN inference on encrypted data and help mitigate such concerns. However, encrypted CNN inference faces the fundamental challenge of optimizing the computations to achieve an acceptable trade-off between accuracy and practical computational feasibility. Current approaches for encrypted CNN inference demonstrate feasibility typically on smaller images (e.g., MNIST and CIFAR-10 datasets) and shallow neural networks. This work is the first to show encrypted inference results on a real-world dataset for melanoma detection with large-sized images of skin lesions based on the Cheon-Kim-Kim-Song (CKKS) encryption scheme available in the open-source HElib library. The practical challenges related to encrypted inference are first analyzed and inference experiments are conducted on encrypted MNIST images to evaluate different optimization strategies and their role in determining the throughput and latency of the inference process. Using these insights, a modified LeNet-like architecture is designed and implemented to achieve the end goal of enabling encrypted inference on melanoma dataset. The results demonstrate that 80% classification accuracy can be achieved on encrypted skin lesion images (security of 106 bits) with a latency of 51 seconds for single image inference and a throughput of 18,000 images per hour for batched inference, which shows that privacy-preserving machine learning as a service (MLaaS) based on encrypted data is indeed practically feasible.