A significant drawback of enzyme use in industrial applications is its lack of stability. Graphene oxide (GO) has previously been investigated for enzyme immobilization and enhancement of enzymatic catalysis. Microbial transglutaminase (MTG) is an enzyme that is used to modify food proteins, increase durability of textiles, and crosslink hydrogels for drug delivery. We tested the effects of adding GO and partially reduced GO (pRGO) to water solutions of gelatin and then crosslinking it with MTG, measuring both the resulting gelatin modulus and then the time it took for the onset of gelation. We found that the presence of pRGO in a gelatin-MTG-water mixture (when using 0.75 g MTG in 10 ml of gelatin solution) significantly increases the modulus by 60% more than the control. Using this same concentration of MTG, we measured the onset of gelation time and found that pRGO in gelatin solution reduces the onset of gelation time by nearly 50% while inducing a very large increase in viscosity by three orders of magnitude, whereas the addition of GO increases the onset of gelation time by 33% and decreases the viscosity of the gel by more than one order of magnitude. The very large enhancement by pRGO of the viscosity may be due to pRGO’s electron withdrawing ability and/or may also be due to adsorption of gelatin to the pRGO platelets which effectively increases the crosslinking density through non-enzymatic processes assisting the enzymatic activity.