The magnetic properties of amorphous Fe–Ni–B based metallic glass nanostructures were investigated. The nanostructures underwent a spin-glass transition at temperatures below 100 K and revealed an irreversible temperature following the linear de Almeida–Thouless dependence. When the nanostructures were cooled below 25 K in a magnetic field, they exhibited an exchange bias effect with enhanced coercivity. The observed onset of exchange bias is associated with the coexistence of the spin-glass phase along with the appearance of another spin-glass phase formed by oxidation of the structurally disordered surface layer, displaying a distinct training effect and cooling field dependence. The latter showed a maximum in exchange bias field and coercivity, which is probably due to competing multiple equivalent spin configurations at the boundary between the two spin-glass phases.