We demonstrate the fabrication of ultra-low-loss, all-fiber Fabry-Perot cavities containing a nanofiber section, optimized for cavity quantum electrodynamics. By continuously monitoring the finesse and fiber radius during fabrication of a nanofiber between two fiber Bragg gratings, we are able to precisely evaluate taper transmission as a function of radius. The resulting cavities have an internal round-trip loss of only 0.31% at a nanofiber waist radius of 207 nm, with a total finesse of 1380, and a maximum expected internal cooperativity of $sim$ 1050 for a cesium atom on the nanofiber surface. Our ability to fabricate such high-finesse nanofiber cavities may open the door for the realization of high-fidelity scalable quantum networks.