The structure of Al atoms deposited on the GaAs (110) surface has been studied using a first- principles pseudopotential energy minimization calculation. The lowest energy configurations are determined by minimizing the total energy of the system with respect to its structural degrees of freedom. The most stable configuration is such that Al atoms replace the second (or deeper) layer Ga atoms. At temperatures where this reaction cannot be activated, two important processes are found to exist. In the low coverage limit, atoms favor twofold sites connecting an As atom and a Ga atom (in the next zigzag chain) on the surface, forming strong chemical bonds with the substrate. At higher coverages, on the other hand, Al atoms tend to cluster and make new bonds among themselves. The chemisorption energy map over the surface has been obtained and the possible path of the migration of Al atoms for clustering is investigated.