We report results from numerical simulations of star formation in the early universe that focus on the dynamical behavior of metal-free gas under different initial and environmental conditions. In particular we investigate the role of turbulence, which is thought to ubiquitously accompany the collapse of high-redshift halos. We distinguish between two main cases: the birth of Population III.1 stars - those which form in the pristine halos unaffected by prior star formation - and the formation of Population III.2 stars - those forming in halos where the gas is still metal free but has an increased ionization fraction. This latter case can arise either from exposure to the intense UV radiation of stellar sources in neighboring halos, or from the high virial temperatures associated with the formation of massive halos, that is, those with masses greater than ? 108 M?. We find that turbulent primordial gas is highly susceptible to fragmentation in both cases, even for turbulence in the subsonic regime, i.e. for rms velocity dispersions as low as 20 % of the sound speed. Contrary to our original expectations, fragmentation is more vigorous and more widespread in pristine halos compared to pre-ionized ones. We therefore predict Pop III.1 stars to be on average of somewhat lower mass, and form in larger groups, than Pop III.2 stars. We find that fragment masses cover over two orders of magnitude, indicating that the resulting Population III initial mass function was significantly extended in mass as well. Our results suggest that the details of the fragmentation process depend on the local properties of the turbulent velocity field and hence we expect considerable variations in the resulting stellar mass spectrum in different halos. In particular, the lowest-mass objects in our sample should have survived to the present day and could potentially provide a unique record of the physical conditions of stellar birth in the primordial universe. This prompts the need for a large, high-resolution study of the formation of dark matter minihalos that is capable of resolving the turbulent flows in the gas at the moment when the baryons become self-gravitating. This would help determine which, if any, of the initial conditions presented in our study are realized in nature. Show Partial Abstract