The uptake of glyoxal (Gly) on 28 different samples with varying mineralogical origins, such as clays, mineral proxies, and natural dusts from the major arid regions of the Earth, was determined. Experiments were performed at ambient temperature inside a Knudsen flow reactor coupled to a molecular-beam-sampling mass spectrometer. The objective of using a such high number of mineral surfaces (screening approach) was to identify composition-activity relationships (CAR) that link the elemental composition of the mineral samples with the Gly uptake and to evaluate the impact of particle size on Gly uptake. Three parameters were measured to meet these objectives: (i) the initial uptake coefficient (gamma 0), (ii) the quasi-steady-state uptake coefficient (gamma(q-ss)), and (iii) the number of Gly molecules taken up (or uptake quantity, Ns, in molecules cm(-2)). In all of the various investigated Gly-surface systems, Gly uptake was found to be predominantly irreversible. The gamma 0 values measured indicate that Gly is selectively uptaken on surface sites terminated with hydroxyl groups. The abundance of elements, such as Ti, Al, and Ca, was evidenced to play a dominant role in the uptake of Gly on mineral dusts. In particular, the CAR trends observed were: gamma(0) = ( 0.05 +/- 0.02 ) + ( 7.2 +/- 2.0 ) x Ti/Si , gamma(q-ss) = ( 16.7 +/- 2.2 ) x 10(-7) - ( 20.0 +/- 6.5 ) x exp([( - 15 +/- 9 ) x ( Al + Ca ) / Si ]) , where the relative abundance of the elements is expressed in % wt for a constant Gly concentration of 70 ppb. Our results suggest that Gly is taken up on mineral dust particles, and thus, this heterogeneous process can contribute to the formation of secondary organic aerosols (SOA) in the atmosphere. Furthermore, our results reveal the need of composition-activity relationships for atmospheric pollutants that if implemented in atmospheric models will assist in better simulating the atmospheric aging of mineral dust. Finally, the steady-state uptake coefficients of Gly on Gobi natural dust were determined as a function of Gly concentration and results were found to be well represented by the expression gamma(q-ss) = (1.3 +/- 0.4) x 10(-6) + (5.1 +/- 0.2) x 10(-5) [Gly](-(0.85 +/- 0.04)), where [Gly] is expressed in ppb and the uptake coefficients are normalized by the specific surface area of the samples. Under atmospherically relevant Gly concentrations, the uptake coefficient values were in the range 10(-3)-10(-4), and thus its heterogeneous removal on dust particles is expected to be a significant atmospheric loss process for Gly, comparable to or even higher than gas-phase degradation by OH radicals or photolysis.