The capability of three analytical techniques, inductively coupled plasma-atomic emission spectrometry (ICP-AES), anodic stripping voltammetry (ASV), and instrumental neutron-activation analysis (INAA) have been compared for the determination of Cd, Fe, Pb, and Zn in airborne particulate matter, collected on cellulose filters, from the atmosphere of the large area of Thessaloniki, Greece. Two procedures were tested for quantitative leaching of these elements from the filters before ICP-AES and ASV, digestion with aqua regia in a Teflon autoclave, after dissolution of the organic matter with HClO4 under ambient conditions, and ultrasonic extraction with a mixture of HNO3 and HCl. Validation of the leaching and digestion procedures revealed that digestion in the autoclave is more effective, especially for Fe. The concentrations of these elements over a decade in both industrial and urban areas of the investigated region are compared.