We present the first uniform treatment of long duration gamma-ray burst (GRB) host galaxy detections and upper limits over the redshift range 3<z<5, a key epoch for observational and theoretical efforts to understand the processes, environments, and consequences of early cosmic star formation. We contribute deep imaging observations of 13 GRB positions yielding the discovery of eight new host galaxies. We use this dataset in tandem with previously published observations of 31 further GRB positions to estimate or constrain the host galaxy rest-frame ultraviolet (UV; 1600 A) absolute magnitudes M_UV. We then use the combined set of 44 M_UV estimates and limits to construct the M_UV luminosity function (LF) for GRB host galaxies over 3<z<5 and compare it to expectations from Lyman break galaxy (LBG) photometric surveys with the Hubble Space Telescope. Adopting standard prescriptions for the luminosity dependence of galaxy dust obscuration (and hence, total star formation rate), we find that our LF is compatible with LBG observations over a factor of 600x in host luminosity, from M_UV = -22.5 mag to >-15.6 mag, and with extrapolations of the assumed Schechter-type LF well beyond this range. We review proposed astrophysical and observational biases for our sample, and find they are for the most part minimal. We therefore conclude, as the simplest interpretation of our results, that GRBs successfully trace UV metrics of cosmic star formation over the range 3<z<5. Our findings suggest GRBs are providing an accurate picture of star formation processes from z ~3 out to the highest redshifts.