(abridged) We use large cosmological simulations to study the origin of primordial star-forming clouds in a Lambda CDM universe, by following the formation of dark matter halos and the cooling of gas within them. To model the physics of chemically pristine gas, we employ a non-equilibrium treatment of the chemistry of 9 species and include cooling by molecular hydrogen. We explore the hierarchical growth of bound structures forming at redshifts z = 25 - 30 with total masses in the range 10^5 - 10^6 Msun. The complex interplay between the gravitational formation of dark halos and the thermodynamic and chemical evolution of the gas clouds compromises analytic estimates of the critical H2 fraction. Dynamical heating from mass accretion and mergers opposes relatively inefficient cooling by molecular hydrogen, delaying the production of star-forming clouds in rapidly growing halos. We also investigate the impact of photo-dissociating ultra-violet (UV) radiation on the formation of primordial gas clouds. We consider two extreme cases by first including a uniform radiation field in the optically thin limit and secondly by accounting for the maximum effect of gas self-shielding in virialized regions. In both the cases we consider, the overall impact can be described by computing an equilibrium H2 abundance for the radiation flux and defining an effective shielding factor. Based on our numerical results, we develop a semi-analytic model of the formation of the first stars, and demonstrate how it can be coupled with large N-body simulations to predict the star formation rate in the early universe.