Recent observations have shown that the characteristic luminosity of the rest-frame ultraviolet (UV) luminosity function does not significantly evolve at 4 < z < 7 and is approximately M*_UV ~ -21. We investigate this apparent non-evolution by examining a sample of 178 bright, M_UV < -21 galaxies at z=4 to 7, analyzing their stellar populations and host halo masses. Including deep Spitzer/IRAC imaging to constrain the rest-frame optical light, we find that M*_UV galaxies at z=4-7 have similar stellar masses of log(M/Msol)=9.6-9.9 and are thus relatively massive for these high redshifts. However, bright galaxies at z=4-7 are less massive and have younger inferred ages than similarly bright galaxies at z=2-3, even though the two populations have similar star formation rates and levels of dust attenuation. We match the abundances of these bright z=4-7 galaxies to halo mass functions from the Bolshoi Lambda-CDM simulation to estimate the halo masses. We find that the typical halo masses in ~M*_UV galaxies decrease from log(M_h/Msol)=11.9 at z=4 to log(M_h/Msol)=11.4 at z=7. Thus, although we are studying galaxies at a similar mass across multiple redshifts, these galaxies live in lower mass halos at higher redshift. The stellar baryon fraction in units of the cosmic mean Omega_b/Omega_m rises from 5.1% at z=4 to 11.7% at z=7; this evolution is significant at the ~3-sigma level. This rise does not agree with simple expectations of how galaxies grow, and implies that some effect, perhaps a diminishing efficiency of feedback, is allowing a higher fraction of available baryons to be converted into stars at high redshifts.