Two-step sintering (TSS) consists of a high-temperature step and immediate cooling to a sintering temperature for an extended sintering time, where grain growth is suppressed by severe densification during the high-temperature step. TSS is adopted to enhance mechanical properties of electrospun ceramic nanofibers (CNFs), a class of porous ceramics used for environmental remediation, optoelectronics, and filtration. PVP and Ga(NO3)3 nanofiber mesh, provided by Lawrence Livermore National Laboratory, was shaped, oxidized, and two-step sintered to form a nanocrystalline β-Ga2O3 CNF tube using a high-temperature step of 1,000oC. Sintering temperatures and times varied from 625oC to 875oC for 1 hour to 4 hours. A minimum sample size of 26 tubes from each heat treatment were diametrally compressed and compared, with Weibull statistics, to isothermally sintered tubes, treated at 1,000oC for 1 hour with an average yield strength of 3.36 kPa. CNFs exhibit a pseudo-plastic transition from brittle to cellular stress-strain behavior, resulting from successive brittle fiber failures and pore crushing. TSS successfully strengthens the CNF tubes to an average yield strength of 5.72 kPa with a 2 hour, 875oC sintering. X-ray diffraction (XRD) crystallite measurements and scanning electron microscopy (SEM) showed that TSS suppressed grain growth and formed a nanocrystalline microstructure. Further SEM image processing revealed yield stress is negatively correlated with porosity, fiber diameter, and tube diameter.