We utilize the newly acquired, ultra-deep WFC3/IR observations over the Hubble Ultra Deep Field (HUDF) to search for star-forming galaxies at z ~ 8-8.5, only 600 million years from recombination, using a Y 105-dropout selection. The new 4.7 arcmin2 WFC3/IR observations reach to ~28.8 AB mag (5 Delta *s) in the Y 105 J 125 H 160 bands. These remarkable data reach ~1.5 AB mag deeper than the previous data over the HUDF, and now are an excellent match to the HUDF optical ACS data. For our search criteria, we use a two-color Lyman break selection technique to identify z ~ 8-8.5Y 105-dropouts. We find five likely z ~ 8-8.5 candidates. The sources have H 160-band magnitudes of ~28.3 AB mag and very blue UV-continuum slopes, with a median estimated Delta *b of -2.5 (where f Delta *l Delta *l Delta *b). This suggests that z ~ 8 galaxies are not only essentially dust free but also may have very young ages or low metallicities. The observed number of Y 105-dropout candidates is smaller than the 20 +/- 6 sources expected assuming no evolution from z ~ 6, but is consistent with the five expected extrapolating the Bouwens et al. luminosity function (LF) results to z ~ 8. These results provide evidence that the evolution in the LF seen from z ~ 7 to z ~ 3 continues to z ~ 8. The remarkable improvement in the sensitivity of WFC3/IR has enabled Hubble Space Telescope to cross a threshold, revealing star-forming galaxies at z~ 8-9.