SnSe emerges as a new class of thermoelectric materials since the recent discovery of an ultrahigh thermoelectric figure of merit in its single crystals. Achieving such performance in the polycrystalline counterpart is still challenging and requires fundamental understandings of its electrical and thermal transport properties as well as structural chemistry. Here we demonstrate a new strategy of improving conversion efficiency of bulk polycrystalline SnSe thermoelectrics. We show that PbSe alloying decreases the transition temperature between Pnma and Cmcm phases and thereby can serve as a means of controlling its onset temperature. Along with 1% Na doping, delicate control of the alloying fraction markedly enhances electrical conductivity by earlier initiation of bipolar conduction while reducing lattice thermal conductivity by alloy and point defect scattering simultaneously. As a result, a remarkably high peak ZT of ∼1.2 at 773 K as well as average ZT of ∼0.5 from RT to 773 K is achieved for Na0.01(Sn1-xPbx)0.99Se. Surprisingly, spherical-aberration corrected scanning transmission electron microscopic studies reveal that NaySn1-xPbxSe (0 < x ≤ 0.2; y = 0, 0.01) alloys spontaneously form nanoscale particles with a typical size of ∼5-10 nm embedded inside the bulk matrix, rather than solid solutions as previously believed. This unexpected feature results in further reduction in their lattice thermal conductivity.