Stiff, strong and tough ultrafine polyethylene fibers that rival the best high performance fibers like Spectra, but with diameters less than one micron, are fabricated for the first time by "gel-electrospinning". In this process, solution concentration and process temperatures are chosen to induce the formation of gel filaments "in flight", which are subsequently drawn at high rates as a consequence of the whipping instability. The resulting submicron diameter fibers exhibited Young's moduli of 73 +/- 13 GPa, yield strengths of 3.5 +/- 0.6 GPa, and toughnesses of 1.8 +/- 0.3 GPa, on average. Among the smallest fibers examined, one with a diameter of 490 +/- 50 nm showed a Young's modulus of 110 Angstrom +/- 16 GPa, ultimate tensile strength of 6.3 +/- 0.9 GPa, and toughness of 2.1 +/- 0.3 GPa, a combination of mechanical properties that is unparalleled among polymer nanofibers to date. The correlation of stiffness, strength and toughness with fiber diameter is attributed to increased crystallinity and crystallite orientation, and to geometrical constraints on crack size in accordance with Griffith's theory. The gel-electrospinning process improves the prospects for production of such fibers at scale.