The generation of biomaterials with adequate biomechanical and structural properties remains a challenge in tissue engineering and regenerative medicine. Earlier research has shown that nanostructuration and cross-linking techniques improved the biomechanical and structural properties of different biomaterials. Currently, uncompressed and nanostructured fibrin-agarose hydrogels (FAH and NFAH, respectively) have been used successfully in tissue engineering. The aim of this study was to investigate the possibility of improving the structural and biomechanical properties of FAH and NFAH by using 0.25% and 0.5% (v/v) glutaraldehyde (GA) as a cross-linker. These non-cross-linked and cross-linked hydrogels were subjected to structural, rheological and ex vivo biocompatibility analyses. Our results showed that GA cross-linking induced structural changes and significantly improved the rheological properties of FAH and NFAH. In addition, ex vivo biocompatibility analyses demonstrated viable cells in all conditions, although viability was more compromised when 0.5% GA was used. Our study demonstrates that it is possible to control fiber density and hydrogel porosity of FAH and NFAH by using nanostructuration or GA cross-linking techniques. In conclusion, hydrogels cross-linked with 0.25% GA showed promising structural, biochemical and biological properties for use in tissue engineering.