The relic abundance of a particle species that was once in thermal equilibrium in the expanding Universe depends upon a competition between the annihilation rate of the species and the expansion rate of the Universe. Assuming that the Universe is radiation dominated at early times the relic abundance is easy to compute and well known. At times earlier than about 1 sec after the bang there is little or no evidence that the Universe had to be radiation dominated, although that is the simplest–and standard–assumption. Because early-Universe relics are of such importance both to particle physics and to cosmology, we consider in detail three nonstandard possibilities for the Universe at the time a species’ abundance froze in: energy density dominated by shear (i.e., anisotropic expansion), energy density dominated by some other nonrelativistic species, and energy density dominated by the kinetic energy of the scalar field that sets the gravitational constant in a Brans-Dicke-Jordan cosmological model. In the second case the relic abundance is less than the standard value, while in the other two cases it can be enhanced by a significant factor. We also mention two other more exotic possibilities for enhancing the relic abundance of a species–a larger value of Newton’s constant at early times (e.g., as might occur in superstring or Kaluza-Klein theories) or a component of the energy density at early times with a very stiff equation of state (p>ρ/3), e.g., a scalar field φ with potential V(φ)=β‖φ‖n with n>4. Our results have implications for dark-matter searches and searches for particle relics in general.