Long-duration gamma-ray bursts ( GRBs ) provide a premier tool for studying high-redshift star-forming galaxies thanks to their extreme brightness and association with massive stars . Here we use GRBs to study the galaxy mass-metallicity ( M _ { * } - Z ) relation at z \sim 3 - 5 , where conventional direct metallicity measurements are extremely challenging . We use the interstellar medium metallicities of long-duration GRB hosts derived from afterglow absorption spectroscopy ( Z \approx 0.01 - 1 Z _ { \odot } ) , in conjunction with host galaxy stellar masses determined from deep Spitzer 3.6 \mu m observations of 20 GRB hosts . We detect about 1/4 of the hosts with M _ { AB } ( I ) \approx - 21.5 to -22.5 mag , and place a limit of M _ { AB } ( I ) \gtrsim - 19 mag on the remaining hosts from a stacking analysis . Using a conservative range of mass-to-light ratios for simple stellar populations ( with ages of 70 Myr to \sim 2 Gyr ) , we infer the host stellar masses and present the galaxy mass-metallicity measurements at z \sim 3 - 5 ( \langle z \rangle \approx 3.5 ) . We find that the detected GRB hosts , with M _ { * } \approx 2 \times 10 ^ { 10 } M _ { \odot } , display a wide range of metallicities , but that the mean metallicity at this mass scale , Z \approx 0.1 Z _ { \odot } , is lower than measurements at z \lesssim 3 . Combined with stacking of the non-detected hosts ( with M _ { * } \lesssim 4 \times 10 ^ { 9 } M _ { \odot } and Z \lesssim 0.03 Z _ { \odot } ) , we find evidence for the existence of an M _ { * } - Z relation at z \sim 3.5 and continued evolution of this relation to systematically lower metallicities from z \sim 2 .