We present the first spectroscopic measurements of the [O III] 5007 Å line in two z ~ 3.1 Lyalpha emitting galaxies (LAEs) using the new near-infrared instrument LUCIFER1 on the 8.4 m Large Binocular Telescope. We also describe the optical imaging and spectroscopic observations used to identify these LAEs. Using the [O III] line we have measured accurate systemic redshifts for these two galaxies, and discovered a velocity offset between the [O III] and Lyalpha lines in both, with the Lyalpha line peaking 342 and 125 km s-1 redward of the systemic velocity. These velocity offsets imply that there are powerful outflows in high-redshift LAEs. They also ease the transmission of Lyalpha photons through the interstellar medium and intergalactic medium around the galaxies. By measuring these offsets directly, we can refine both Lyalpha-based tests for reionization, and Lyalpha luminosity function measurements where the Lyalpha forest affects the blue wing of the line. Our work also provides the first direct constraints on the strength of the [O III] line in high-redshift LAEs. We find [O III] fluxes of 7 and 36 ×10-17 erg s-1 cm-2 in two z ~ 3.1 LAEs. These lines are strong enough to dominate broadband flux measurements that include the line (in this case, Ks -band photometry). Spectral energy distribution fits that do not account for the lines would therefore overestimate the 4000 Å (and/or Balmer) break strength in such galaxies, and hence also the ages and stellar masses of such high-z galaxies.