In late 2019, COVID-19, a severe respiratory disease, emerged, and since then, the world has been facing a deadly pandemic caused by it. This ongoing pandemic has had a significant effect on different aspects of societies. The uncertainty around the number of daily cases made it difficult for decision-makers to control the outbreak. Deep Learning models have proved that they can come in handy in many real-world problems such as healthcare ones. However, they require a lot of data to learn the features properly and output an acceptable solution. Since COVID-19 has been a lately emerged disease, there was not much data available, especially in the first stage of the pandemic, and this shortage of data makes it challenging to design an optimized model. To overcome these problems, we first introduce a new dataset with augmented features and then forecast COVID-19 cases with a new approach, using an evolutionary neural architecture search with Binary Bat Algorithm (BBA) to generate an optimized deep recurrent network. Finally, to show our approach's effectiveness, we conducted a comparative study on Iran's COVID-19 daily cases. The results prove our approach's capability to generate an accurate deep architecture to forecast the pandemic cases, even in the early stages with limited data.