At low coverages, the codeposition of Co and As on the GaAs( 100) c (4 X 4) surface results in the formation of two different types of self-assembled nanostructures; one has a "mesa" configuration, and the other a large aspect ratio "nanostripe" configuration. Minimum-energy calculations have been performed on several possible surface reconstructions for the latter configuration. The favored structure has a rather small unit that repeats essentially endlessly along the [I 10] direction. This unit contains one Co atom substituted between adjacent c(4X4) As dimers that straddle a misfit dislocation in the two-dimensional c (4 X 4) lattice. The distorted octahedral bonding around these Co atoms is completed by the addition of three As atoms to the repeat unit. A dip or a valley is formed on each side of the nanostripe by removing As atoms from the substrate. This valley partially relieves the compressive strain along the [110] direction across the nanostripes, and it helps to insure that each Co atom is surrounded by the requisite 18 valence electrons. The detailed atomic structure of the mesas was not determined. However, it is suggested that they are CoAs crystallites with a specific orientation relative to the substrate. (C) 2003 American Vacuum Society.