Being heavily dependent to oil products (mainly gasoline and diesel), the French transport sector is the main emitter of Particulate Matter (PMs) whose critical levels induce harmful health effects for urban inhabitants. We selected three major French cities (Paris, Lyon, and Marseille) to investigate the relationship between the Coronavirus Disease 19 (COVID-19) outbreak and air pollution. Using Artificial Neural Networks (ANNs) experiments, we have determined the concentration of PM2.5 and PM10 linked to COVID-19-related deaths. Our focus is on the potential effects of Particulate Matter (PM) in spreading the epidemic. The underlying hypothesis is that a pre-determined particulate concentration can foster COVID-19 and make the respiratory system more susceptible to this infection. The empirical strategy used an innovative Machine Learning (ML) methodology. In particular, through the so-called cutting technique in ANNs, we found new threshold levels of PM2.5 and PM10 connected to COVID-19: 17.4 µg/m3 (PM2.5) and 29.6 µg/m3 (PM10) for Paris; 15.6 µg/m3 (PM2.5) and 20.6 µg/m3 (PM10) for Lyon; 14.3 µg/m3 (PM2.5) and 22.04 µg/m3 (PM10) for Marseille. Interestingly, all the threshold values identified by the ANNs are higher than the limits imposed by the European Parliament. Finally, a Causal Direction from Dependency (D2C) algorithm is applied to check the consistency of our findings.