When reducing the size of metallic glass samples down the nanoscale regime, experimental studies on the plasticity under uniaxial tension show a wide range of failure modes ranging from brittle to ductile ones. Simulations on the deformation behavior of nanoscaled metallic glasses report an unusual extended strain softening and are not able to reproduce the brittle-like fracture deformation as found in experiments. Using large-scale molecular dynamics simulations we provide an atomistic understanding of the deformation mechanisms of metallic glass nanowires and differentiate the extrinsic size effects and aspect ratio contribution to plasticity. A model for predicting the critical nanowire aspect ratio for the ductile-to-brittle transition is developed. Furthermore, the structure of brittle nanowires can be tuned to a softer phase characterized by a defective short-range order and an excess free volume upon systematic structural rejuvenation, leading to enhanced tensile ductility. The presented results shed light on the fundamental deformation mechanisms of nanoscaled metallic glasses and demarcate ductile and catastrophic failure.