The structure of the $(sqrt{5}timessqrt{5})R26.6^circ$ reconstruction of LaAlO$_3$ (001) has been determined using transmission electron diffraction combined with direct methods. The structure is relatively simple, consisting of a lanthanum oxide termination with one lanthanum cation vacancy per surface unit cell. The electronic structure is unusual since a fractional number of holes or atomic occupancies per surface unit cell are required to achieve charge neutrality. Density functional calculations indicate that the charge compensation mechanism occurs by means of highly delocalized holes. The surface contains no oxygen vacancies and with a better than 99% confidence level, the holes are not filled with hydrogen. The reconstruction can be understood in terms of expulsion of the more electropositive cation from the surface followed by an increased covalency between the remaining surface lanthanum atoms and adjacent oxygen atoms.