Colloidal crystallization of nanoparticles with different functionalities into multicomponent assemblies provides a route to new classes of ordered nanocomposites with novel properties tunable by the choice of the constituent building blocks. While theories based on hard sphere approximation predict crystallization of only a few stable binary phases (NaCl-, AlB(2)- and NaZn(13)-type), we find that additional polymorphs of lower packing density are possible. We demonstrate that PbSe and Pd nanoparticles can be reproducibly crystallized into two polymorphs with AB(13) stoichiometry. One polymorph is isostructural with the intermetallic compound NaZn(13) and is consistent with dense packing of hard spheres driven by entropy. The second unanticipated polymorph is of lower packing density. This observation underscores the shortcomings of applying simple space-filling principles to the crystallization of organically passivated nanocrystals and further motivates the development of models that incorporate combinations of hard-sphere, van der Waals, dipolar, and hydrophobic forces. This work demonstrates that ordered periodic structures with lower packing density are achievable and provides the first example of a binary semiconductor-metal superlattice using a combination of PbSe-Pd nanocrystals.