The first dark matter halos typically originated in the redshift range 30-70, at a time of 30-100 million years. This is based on assuming that the initial variations in the density of the universe at small scales, for which we have no observational data, are comparable to those at large scales, for which we have ample observational data (e.g. the cosmic microwave background and large-scale structure). The particular time is solely a function of how long it took density fluctuations to grow in amplitude from their minuscule initial values of about one part in $10^{4}$ up to the $\mathcal{O}(1)$ values required for regions of excess density to collapse into halos.
More specifically, I did some quick calculations using some CLASS-generated power spectra I had lying around. Suppose the minimum halo mass is around an earth mass (a typical assumption for cold dark matter, but the precise value doesn't affect the result much, as long as it's small). Then $1\sigma$ density excesses reach the "spherical collapse" threshold around redshift 15. That means that under the assumption of spherical symmetry, that is the time when they would collapse to form halos. Similarly, $2\sigma$ excesses collapse around redshift 33, $3\sigma$ excesses around redshift 52, and $4\sigma$ excesses around redshift 72.
Note that the story is different for halos large enough to form galaxies inside them. If I repeat the calculation for a mass scale of (let's say) $10^7$ solar masses, the result is that $1\sigma$ density excesses at this mass scale collapse around redshift 4, $2\sigma$ around redshift 10, $3\sigma$ around redshift 15, and $4\sigma$ around redshift 20.
Also, different assumptions about the amplitudes of initial density variations at small scales can change the formation time of the smallest halos. These initial fluctuations are believed to have been seeded during inflation, and inflationary physics are pretty poorly constrained. If you make the initial variations more extreme, you can make your cosmology form dark matter halos as early as you want. Or can you? During the radiation epoch (before a redshift of about 3400 or a time of about 52000 years), there are no peculiar gravitational forces. The radiation's gravitational influence dominates, and its pressure keeps it homogeneous. You can't really make a gravitationally bound dark matter halo where radiation dominates.