Simultaneous incorporation of cellulose nanocrystals (CNCs) and chitin nanofibers (ChNFs) into a polyvinyl alcohol (PVA) matrix opens possibilities for customization of more environmentally friendly composite materials. When used in tricomponent composite hydrogels, the opposite surface charges on CNCs and ChNFs lead to the construction of beneficial nanofiber structures. In this work, composite hydrogels containing CNCs, ChNFs, or their mixtures are produced using cyclic freeze-thaw (FT) treatments. When considering different compositions and FT cycling, tricomponent composite hydrogels containing a specific ratio of CNCs/ChNFs are shown to have promising mechanical performance in comparison to other samples. These results together with results from water absorption, rheological, and light scattering studies suggest that the CNC/ChNF structures produced property improvement by concurrently accessing the stronger interfacial interactions between CNCs and PVA and the longer lengths of the ChNFs for load transfer. Overall, these results provide insight into using electrostatically driven nanofiber structures in nanocomposites.