A new homogenization theory to model the mechanical response of hyperelastic solids reinforced by a random distribution of aligned cylindrical fibers is proposed. The central idea is to devise a special class of microstructures—by means of an iterated homogenization procedure in finite elasticity together with an exact dilute result for sequential laminates—that allows to compute exactly the macroscopic response of the resulting fiber-reinforced materials. The proposed framework incorporates direct microstructural information up to the two-point correlation functions, and requires the solution to a Hamilton–Jacobi equation with the fiber concentration and the macroscopic deformation gradient playing the role of “time” and “spatial” variables, respectively. In addition to providing constitutive models for the macroscopic response of fiber-reinforced materials, the proposed theory also gives information about the local fields in the matrix and fibers, which can be used to study the evolution of microstructure and the development of instabilities. As a first application of the theory, closed-form results for the case of Neo-Hookean solids reinforced by a transversely isotropic distribution of anisotropic fibers are worked out. These include a novel explicit criterion for the onset of instabilities under general finite-strain loading conditions.