Parkinson's disease (PD) is one of the most serious and challenging neurodegenerative disorders to diagnose. Clinical diagnosis on observing motor symptoms is the gold standard, yet by this point nerve cells are degenerated resulting in a lower efficacy of therapeutic treatments. In this study, we introduce a deep-learning approach based on a recently-proposed 20-Layer Convolutional Neural Network (CNN) applied on the visual realization of the Wavelet domain of a resting-state EEG. The proposed approach was able to efficiently and accurately detect PD as well as distinguish subjects with PD on medications from subjects who are off medication. The gradient-weighted class activation mapping (Grad-CAM) was used to visualize the features based on which the approach provided the predictions. A significantly high accuracy, sensitivity, specificity, AUC, and Weighted Kappa Score up to 99.9% were achieved and the visualization of the regions in the Wavelet images that contributed to the deep-learning approach decisions was provided. The proposed framework can then serve as an effective computer-aided diagnostic tool that will support physicians and scientists in further understanding the nature of PD and providing an objective and confident opinion regarding the clinical diagnosis of the disease.