We performed a detailed investigation of the oxidation of the technologically relevant GaAs(001)-beta 2(2x4) surface via density functional calculations. The purpose is to gain insights on the atomistic mechanisms and local bondings that underlie the degradation of the surface properties once exposed to oxygen. The study comprises the adsorption of single O atoms, through the sampling of several adsorption sites, and the subsequent formation of the O adsorbate at increasing coverage by taking into account multiple-atom adsorption. Based on the evaluation of the energetics and the structural properties of the atomistic models generated, the results here reported delineate a consistent picture of the initial stage of the surface oxidation: (i) at low coverage, in the limit of single O insertions, oxygen is incorporated on the surface forming a twofold-bridging Ga-O-As bond; (ii) at increasing coverage, as multiple O atoms are involved, this is accompanied by the formation of a threefold-coordinated bond (with two Ga and one As atoms); (iii) the latter has important implications regarding the electronic properties of the adsorbate since this O bonding may result in the formation of As dangling bonds. Moreover, a clear trend of increased energy gain for the incorporation of neighboring O atoms compared to single O insertions indicates that the formation of oxide clusters is favored over a regime of uniform oxidation. Our findings provide a detailed description of the O bonding and stress the importance of modeling the adsorption of multiple O atoms for an accurate description of the surface oxidation.