Self-assembling peptide amphiphiles (PAs) can form hierarchically ordered membranes when brought in contact with aqueous polyelectrolytes of the opposite charge by rapidly creating a diffusion barrier composed of filamentous nanostructures parallel to the plane of the incipient membrane. Following this event, osmotic forces and charge complexation template nanofiber growth perpendicular to the plane of the membrane in a dynamic self-assembly process. In this work, we show that this hierarchical structure requires strong interactions between PA molecules and polyelectrolyte molecules, suggesting the importance of rapid diffusion barrier formation. Strong interactions are introduced here through the use of heparin-binding PAs with heparin and also with polyelectrolytes of varying charge density. Small angle x-ray scattering shows that in the case of weak PA-polyelectrolyte interaction, membranes formed display a cubic phase ordering on the nanoscale that likely results from clusters of PA nanostructures surrounded by polyelectrolyte chains.