A model is proposed describing the effect of crack bridging on the fracture toughness of ceramic-based nanocomposites reinforced with hybrid graphene/alumina nanofibers. Within the model, a mode I crack propagates normally to a system of aligned inclusions, whose pullout from the ceramic matrix in the wake of the crack toughens the composite. The dependences of the fracture toughness on the graphene content and the sizes of the inclusions are calculated in the exemplary case of yttria stabilized zirconia based composites. The calculations predict that if crack bridging is the dominant mechanism during crack growth, the maximum toughening can be achieved in the case of long nanofibers provided that the latter do not rupture and adhere well to the matrix. The model shows good correlation with the experimental data at low graphene concentrations.