Over 500 K (per year) cervical cancer cases are reported with a high mortality rate (6–9%). Automatically detecting cervical cancer using the Computer-Aided Diagnosis (CAD) tool at an early stage is important since it leads to successful treatment as pathologists. In this paper, we propose a tool that classifes cervical cancer cases from Pap smear cytology images using deep features. The proposed tool constitutes a Convolutional Neural Network (CNN) and a metaheuristic evolutionary algorithm called Opposition-based Harmony Search Algorithm (O-bHSA) for deep feature section. These features are classifed using standard classifers: SVM, MLP, and KNN. On two diferent publicly available datasets: Pap smear and liquid-based cytology, the proposed tool outperforms not only seven well-known optimization algorithms but also state-of-the-art methods. Codes are publicly available on GitHub.