Models of the decoupling of baryons and photons during the recombination epoch predict the existence of a large-scale velocity offset between baryons and dark matter at later times, the so-called streaming velocity. In this paper, we use high resolution numerical simulations to investigate the impact of this streaming velocity on the spin and shape distributions of high-redshift minihalos, the formation sites of the earliest generation of stars. We find that the presence of a streaming velocity has a negligible effect on the spin and shape of the dark matter component of the minihalos. However, it strongly affects the behaviour of the gas component. The most probable spin parameter increases from $sim$0.03 in the absence of streaming to $sim$0.15 for a run with a streaming velocity of three times $sigma_{rm rms}$, corresponding to 1.4 km,s$^{-1}{}$ at redshift $z=15$. The gas within the minihalos becomes increasingly less spherical and more oblate as the streaming velocity increases, with dense clumps being found at larger distances from the halo centre. The impact of the streaming velocity is also mass-dependent: less massive objects are influenced more strongly, on account of their shallower potential wells. The number of halos in which gas cooling and runaway gravitational collapse occurs decreases substantially as the streaming velocity increases. However, the spin and shape distributions of gas that does manage to cool and collapse are insensitive to the value of the streaming velocity and we therefore do not expect the properties of the stars that formed from this collapsed gas to depend on the value of the streaming velocity. The spin and shape of this central gas clump are uncorrelated with the same properties measured on the scale of the halo as a whole.