Hydrogels have emerged as promising materials for bioprinting and many other biomedical applications due to their high degree of biocompatibility and ability to support and/or modulate cell viability and function. Yet, many hydrogel bioinks have suffered from low efficiency due to limitations on accessible printing speeds, often limiting cell viability and/or the constructs which can be generated. In this study, a highly extensible bioink system created by modulating the rheology of physically crosslinked hydrogels comprising hydrophobically-modified cellulosics and either surfactants or cyclodextrins is reported. It is demonstrated that these hydrogels are highly shear-thinning with broadly tunable viscoelasticity and stress-relaxation through simple modulation of the composition. Rheological experiments demonstrate that increasing concentration of rheology-modifying additives yields hydrogel materials exhibiting extensional strain-to-break values up to 2000%, which is amongst the most extensible examples of physically crosslinked hydrogels of this type. The potential of these hydrogels for use as bioinks is demonstrated by evaluating the relationship between extensibility and printability, demonstrating that greater hydrogel extensibility enables faster print speeds and smaller print features. The findings suggest that optimizing hydrogel extensibility can enhance high-speed 3D bioprinting capabilities, reporting over 5000 fold enhancement in speed index compared to existing works reported for hydrogel-based bioinks in extrusion-based printing.