Utilizing spectroscopic observations taken for the VIMOS Ultra-Deep Survey (VUDS), new observations from Keck/DEIMOS, and publicly available observations of large samples of star-forming galaxies, we report here on the relationship between the star formation rate (SFR) and the local environment ($delta_{gal}$) of galaxies in the early universe ($2<z<5$). Unlike what is observed at lower redshifts ($z<2$), we observe a definite, nearly monotonic increase in the average SFR with increasing galaxy overdensity over more than an order of magnitude in $delta_{gal}$. The robustness of this trend is quantified by accounting for both uncertainties in our measurements and galaxy populations that are either underrepresented or not present in our sample finding that the trend remains significant under all circumstances. This trend appears to be primarily driven by the fractional increase of galaxies in high density environments that are more massive in their stellar content and are forming stars at a higher rate than their less massive counterparts. We find that, even after stellar mass effects are accounted for, there remains a weak but significant SFR-$delta_{gal}$ trend in our sample implying that additional environmentally-related processes are helping to drive this trend. We also find clear evidence that the average SFR of galaxies in the densest environments increases with increasing redshift. These results lend themselves to a picture in which massive gas-rich galaxies coalesce into proto-cluster environments at $zsim3$, interact with other galaxies or with a forming large-scale medium, subsequently using or losing most of their gas in the process, and begin to seed the nascent red sequence that is present in clusters at slightly lower redshifts.