Schottky-barrier formation for Al on GaAs(110) was analyzed theoretically and with the aid of synchrotron-radiation photoemission experiments as a function of the metal coverage. For various Al-overlayer thicknesses we calculated the most stable geometries, using a consistent parameter-free linear combination of atomic orbitals method. Our results show that for an Al monolayer, no density of states appears near the semiconductor charge-neutrality level, in agreement with ultrahigh-resolution photoemission spectra. Theory and experiments agree in obtaining a shrinking of the gap. The theory also shows that the Fermi level is pinned, and the Schottky barrier completely formed, for a coverage of two metal monolayers. For this limit we recover the intrinsic-metal-states model and find good agreement with the Schottky-barrier height for thick metal layers. The experiments reveal some complexity in the intermediate-coverage interface-formation process, with the formation of metal clusters beginning at nominal coverages of 2-4 monolayers; this is somewhat unexpected in the present study because of the low substrate temperature.