Recent LEED and STM studies have revealed dramatic structural changes on the GaAs(001) surface after submonolayer Ge deposition and annealing. In particular, it is found that the surface structure shows a poorly ordered (2 1) and a well-ordered (1 2) superstructure after annealing at about 700 and 875 K, respectively. In this work we report on a first principles pseudopotential study of the atomic geometry, electronic states, and bonding on these structures.