Air pollution monitoring has recently become an issue of utmost importance in our society. Despite the fact that crowdsensing approaches could be an adequate solution for urban areas, they cannot be implemented in rural environments. Instead, deploying a fleet of UAVs could be considered an acceptable alternative. Embracing this approach, this paper proposes the use ofUAVs equipped with off-the-shelf sensors to perform air pollution monitoring tasks. These UAVs are guided by our proposed Pollution-driven UAV Control (PdUC) algorithm, which is based on a chemotaxis metaheuristic and a local particle swarm optimization strategy. Together, they allow automatically performing the monitoring of a specified area using UAVs. Experimental results show that, when using PdUC, an implicit priority guides the construction of pollutionmaps by focusing on areas where the pollutants’ concentration is higher. This way, accurate maps can be constructed in a faster manner when compared to other strategies. The PdUC scheme is compared against various standard mobility models through simulation, showing that it achieves better performance. In particular, it is able to find the most polluted areas with more accuracy and provides a higher coverage within the time bounds defined by the UAV flight time.