Three grades of heat-treated Pyrograf-III carbon nanofibers with diameters of the order of 100-200 nm were tested for their tensile strength by a novel MEMS-based mechanical testing platform. The nominal tensile strengths of the pyrolytically stripped nanofibers and the heat-treated nanofibers followed Weibull distributions with Weibull characteristic strength values between 2.8-3.3 GPa. The true material strengths excluding the hollow fiber cores were twice the nominal strengths. The nanofiber fracture surface had all the elements of brittle fracture with an additional slip of the angled graphene layers comprising the nanofibers. SEM and TEM images of the matching ruptured surfaces pointed to a failure geometry that agrees with the "dixie cup" structure of Pyrograf-III. The change in the mechanical strength and its scatter with heat treatment correlated well with TEM images, which showed increased graphitic content at the expense of the outer turbostratic layer and a loose connectivity of its interface with the inner, originally graphitic, layer.