We present deep Hubble Space Telescope single-star photometry of Leo A in B, V, and I. Our new field of view is offset from the centrally located field observed by Tolstoy et al. (1998) in order to expose the halo population of this galaxy. We report the detection of metal-poor red horizontal branch stars, which demonstrate that Leo A is not a young galaxy. In fact, Leo A is as least as old as metal-poor Galactic Globular Clusters which exhibit red horizontal branches, and are considered to have a minimum age of about 9 Gyr. We discuss the distance to Leo A, and perform an extensive comparison of the data with stellar isochrones. For a distance modulus of 24.5, the data are better than 50% complete down to absolute magnitudes of 2 or more. We can easily identify stars with metallicities between 0.0001 and 0.0004, and ages between about 5 and 10 Gyr, in their post-main-sequence phases, but lack the detection of main-sequence turnoffs which would provide unambiguous proof of ancient (>10 Gyr) stellar generations. Blue horizontal branch stars are above the detection limits, but difficult to distinguish from young stars with similar colors and magnitudes. Synthetic color-magnitude diagrams show it is possible to populate the blue horizontal branch in the halo of Leo A. The models also suggest ~50% of the total astrated mass in our pointing to be attributed to an ancient (>10 Gyr) stellar population. We conclude that Leo A started to form stars at least about 9 Gyr ago. Leo A exhibits an extremely low oxygen abundance, of only 3% of Solar, in its ionized interstellar medium. The existence of old stars in this very oxygen-deficient galaxy illustrates that a low oxygen abundance does not preclude a history of early star formation.