In the early universe, substantial relative "stream" velocities between the gas and dark matter arise due to radiation pressure and persist after recombination. To assess the impact of these velocities on high-redshift structure formation, we carry out a suite of high-resolution adaptive mesh refinement (AMR) cosmological simulations, which use smoothed particle hydrodynamic data sets as initial conditions, converted using a new tool developed for this work. These simulations resolve structures with masses as small as a few 100 M-circle dot, and we focus on the 10(6) M-circle dot "mini-halos" in which the first stars formed. At z approximate to 17, the presence of stream velocities has only a minor effect on the number density of halos below 10(6) M-circle dot, but it greatly suppresses gas accretion onto all halos and the dark matter structures around them. Stream velocities lead to significantly lower halo gas fractions, especially for approximate to 10(5) M-circle dot objects, an effect that is likely to depend on the orientation of a halo's accretion lanes. This reduction in gas density leads to colder, more compact radial profiles, and it substantially delays the redshift of collapse of the largest halos, leading to delayed star formation and possibly delayed reionization. These many differences suggest that future simulations of early cosmological structure formation should include stream velocities to properly predict gas evolution, star formation, and the epoch of reionization.