We perform a comprehensive study of models of dark matter (DM) in a Universe with a non-thermal cosmological history, i.e with a phase of pressure-less matter domination before the onset of big-bang nucleosynethesis (BBN). Such cosmological histories are generically predicted by UV completions that contain gravitationally coupled scalar fields (moduli). We classify the different production mechanisms for DM in this framework, generalizing previous works by considering a wide range of DM masses/couplings and allowing for DM to be in equilibrium with a dark sector. We identify four distinct parametric regimes for the production of relic DM, and derive accurate semi-analytic approximations for the DM relic abundance. Our results are particularly relevant for supersymmetric theories, in which the standard non-thermally produced DM candidates are disfavored by indirect detection constraints. We also comment on experimental signals in this framework, focusing on novel effects involving the power spectrum of DM density perturbations. In particular, we identify a class of models where the spectrum of DM density perturbations is sensitive to the pressure-less matter dominated era before BBN, giving rise to interesting astrophysical signatures to be looked for in the future. A worthwhile future direction would be to study well-motivated theoretical models within this framework and carry out detailed studies of the pattern of expected experimental signals.