It is discovered that complexes of DNA and hydrophobically modified polyelectrolytes form a rigid network of threadlike or fibrous aggregates at the liquid-gas interface whose morphology can dramatically affect the mechanical properties. While mixed solutions of DNA and poly(N,N-diallyl-N,N-dimethylammonium chloride) (PDADMAC) exhibit no notable surface activity, the complexes formed from DNA with poly(N,N-diallyl-N-butyl-N-methylammonium chloride) are surface-active, in contrast to either of the separate components. Further, complexes of DNA and poly(N,N-diallyl-N-hexyl-N-methylammonium chloride) (PDAHMAC) with its longer hydrophobic side chains exhibit pronounced surface activity with values of surface pressures up to 16 mN/m and dynamic surface elasticity up to 58 mN/m. If the PDAHMAC nitrogen to DNA phosphate molar ratio, N/P, is between 0.6 and 3, abrupt compression of the adsorption layer leads unexpectedly to a noticeable decrease of the surface elasticity. The application of imaging techniques reveals that this effect is a consequence of the destruction of a rigid network of threadlike DNA/polyelectrolyte aggregates at the interface. The toroidal aggregates, which are typical for the bulk phase of DNA/PDADMAC solutions in this range of N/P ratios, are not observed in the surface layer. The observed link between the mechanical properties and interfacial morphology of surface-active complexes formed from DNA with hydrophobically modified polyelectrolytes indicates that tuning polyelectrolyte hydrophobicity in these systems may be a means to develop their use in applications ranging from nonviral gene-delivery vehicles to conductive nanowires.