Minerals that contain platinum-group elements (PGEs) and occur in some magmatic Cu-Ni sulfide deposits have been ascribed to crystallization from an originally PGE-rich sulfide liquid. The occurrence of PGE-bearing minerals (PGMs) in some sulfide-undersaturated primitive melts has been envisaged and recently reported, whereas direct crystallization of PGMs in sulfide-saturated silicate magmas is seemingly hindered by strong partitioning of PGE into immiscible sulfide melts. In this study, we discovered abundant nanoparticles containing noble metals in association with sulfide melt inclusions entrapped inside primitive olivine phenocrysts (Fo85–92) from the recent basaltic magma of the Tolbachik volcano (Kamchatka arc, Russia). These nuggets occur in swarms on the surface of the sulfide globules and are represented by native metals, sulfides, and alloys of Pd, Pt, Au, Pb, and Bi. The nuggets on different globules can be either Pd- or Pt-rich nuggets, and the compositions are highly variable, even among adjacent nuggets. We argue that the diffusive supply of Pd from the external nuggets can be responsible for significant uptake of Pd (up to 2 wt%) in the sulfide melt. We consider direct crystallization of PGMs in a primitive basaltic melt undergoing sulfide unmixing, and possibly sulfide breakdown due to oxidation, as another mechanism additional to their “classic” origin from the PGE-rich sulfide melt in response to solidification.