The study of nanocrystalline inorganic nanofibrous membranes (NINMs) with flexibility is one of the most active academic research areas in advanced functional nanofibrous materials. Nonetheless, the role of nanocrystallinity in flexibility has remained uninvestigated until now, according to typical Hall-Petch effects of nanocrystalline metals. Here, we show a surprising brittle-to-flexible-to-brittle transition of zirconia and yttria stabilized zirconia (YSZ) nanofibrous membranes as the grain size and pore size reduce below 26 and 13 nm, respectively. Moreover, classical and inverse Hall-Petch effects were revealed in nanocrystalline zirconia and YSZ nanofibrous systems, which correspond to intragranular and intergranular deformation mechanisms, respectively. Most importantly, the bending deformation mechanism of the flexible nanocrystalline YSZ nanofibrous membranes was proposed from macroscopical membranes to microscopic unit cells, including the slip of fibers, bending of fibers, grain activity, and dislocation motions, which was given for the first time in electrospun flexible NINM materials. Our discovery is fundamentally important for understanding deformation behavior and designing various flexible NINMs as promising candidates in the field of catalysis, supercapacitors, biomaterials, etc.