We investigate the average physical properties and star formation histories ( SFHs ) of the most UV-luminous star-forming galaxies at z \sim 3.7 . Our results are based on the average spectral energy distributions ( SEDs ) , constructed from stacked optical to infrared photometry , of a sample of the 1,913 most UV-luminous star-forming galaxies found in 5.3 square degrees of the NOAO Deep Wide-Field Survey . We find that the shape of the average SED in the rest-optical and infrared is fairly constant with UV luminosity : i.e. , more UV luminous galaxies are , on average , also more luminous at longer wavelengths . In the rest-UV , however , the spectral slope \beta ( \equiv~ { } d { log } F _ { \lambda } / d { log } \lambda ; measured at 0.13 \mum < \lambda _ { rest } < 0.28 \mum ) rises steeply with the median UV luminosity from -1.8 at L \approx L ^ { * } to -1.2 ( L \approx 4 - 5 L ^ { * } ) . We use population synthesis analyses to derive their average physical properties and find that : ( 1 ) L _ { UV } , and thus star-formation rates ( SFRs ) , scale closely with stellar mass such that more UV-luminous galaxies are more massive ; ( 2 ) The median ages indicate that the stellar populations are relatively young ( 200-400 Myr ) and show little correlation with UV luminosity ; and ( 3 ) More UV-luminous galaxies are dustier than their less-luminous counterparts , such that L \approx 4 - 5 L ^ { * } galaxies are extincted up to A ( 1600 ) = 2 mag while L \approx L ^ { * } galaxies have A ( 1600 ) = 0.7 - 1.5 mag . We argue that the average SFHs of UV-luminous galaxies are better described by models in which SFR increases with time in order to simultaneously reproduce the tight correlation between the UV-derived SFR and stellar mass , and their universally young ages . We demonstrate the potential of measurements of the SFR- M _ { * } relation at multiple redshifts to discriminate between simple models of SFHs . Finally , we discuss the fate of these UV-brightest galaxies in the next 1 - 2 Gyr and their possible connection to the most massive galaxies at z \sim 2 .