COVID-19 has had a detrimental impact on normal activities, public safety, and the global financial system. To identify the presence of this disease within communities and to commence the management of infected patients early, positive cases should be diagnosed as quickly as possible. New results from X-ray imaging indicate that images provide key information about COVID-19. Advanced deep-learning (DL) models can be applied to X-ray radiological images to accurately diagnose this disease and to mitigate the effects of a shortage of skilled medical personnel in rural areas. However, the performance of DL models strongly depends on the methodology used to design their architectures. Therefore, deep neuroevolution (DNE) techniques are introduced to automatically design DL architectures accurately. In this paper, a new paradigm is proposed for the automated diagnosis of COVID-19 from chest X-ray images using a novel two-stage improved DNE Algorithm. The proposed DNE framework is evaluated on a real-world dataset and the results demonstrate that it provides the highest classification performance in terms of different evaluation metrics.