We utilize the newly-acquired, ultra-deep WFC3/IR observations over the 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 arcmin**2 WFC3/IR observations reach to ~28.8 AB mag (5 sigma) 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.5 Y_{105}-dropouts. We find 5 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 beta of <~-2.5 (where f_{lambda}propto lambda^{beta}). 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 5 expected extrapolating the Bouwens et al. 2008 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 HST to cross a threshold, revealing star-forming galaxies at z~8-9.