We use all available deep optical ACS and near-IR data over both the HUDF and the two GOODS fields to search for star-forming galaxies at z>~7 and constrain the UV LF within the first 700 Myrs. Our data set includes ~23 arcmin^2 of deep NICMOS J+H data and ~248 arcmin^2 of ground-based (ISAAC+MOIRCS) data, coincident with ACS optical data of greater or equal depths. In total, we find 8 <z>~7.3 z-dropouts in our search fields, but no z~9 J-dropout candidates. A careful consideration of a wide variety of different contaminants suggest an overall contamination level of just ~12% for our z-dropout selection. After performing detailed simulations to accurately estimate the selection volumes, we derive constraints on the UV LFs at z~7 and z~9. For a faint-end slope alpha=-1.74, our most likely values for M*(UV) and phi* at z~7 are -19.8+/-0.4 mag and 1.1_{-0.7}^{+1.7} x 10^{-3} Mpc^{-3}, respectively. Our search results for z~9 J-dropouts set a 1 sigma lower limit on M*(UV) of -19.6 mag assuming that phi* and alpha are the same as their values at slightly later times. This lower limit on M*(UV) is 1.4 mag fainter than our best-fit value at z~4, suggesting that the UV LF has undergone substantial evolution over this time period. No evolution is ruled out at 99% confidence from z~7 to z~6 and at 80% confidence from z~9 to z~7. The inferred brightening in M*(UV) with redshift (i.e., M*(UV) = (-21.02+/-0.09) + (0.36+/-0.08)(z - 3.8)) matches the evolution expected in the halo mass function, if the mass-to-light ratio of halos evolves as ~(1+z)**{-1}. Finally, we consider the shape of the UV LF at z>~5 and discuss the implications of the Schechter-like form of the observed LFs, particularly the unexpected abrupt cut-off at the bright end.