The structure of 55-atom Li-Na and Na-K nanoalloys is determined through combined empirical potential (EP) and density functional theory (DFT) calculations. The potential energy surface generated by the EP model is extensively sampled by using the basin hopping technique, and a wide diversity of structural motifs is reoptimized at the DFT level. A composition comparison technique is applied at the DFT level in order to make a final refinement of the global minimum structures. For dilute concentrations of one of the alkali atoms, the structure of the pure metal cluster, namely, a perfect Mackay icosahedron, remains stable, with the minority component atoms entering the host cluster as substitutional impurities. At intermediate concentrations, the nanoalloys adopt instead a core-shell polyicosahedral (p-Ih) packing, where the element with smaller atomic size and larger cohesive energy segregates to the cluster core. The p-Ih structures show a marked prolate deformation, in agreement with the predictions of jelliumlike models. The electronic preference for a prolate cluster shape, which is frustrated in the 55-atom pure clusters due to the icosahedral geometrical shell closing, is therefore realized only in the 55-atom nanoalloys. An analysis of the electronic densities of states suggests that photoelectron spectroscopy would be a sufficiently sensitive technique to assess the structures of nanoalloys with fixed size and varying compositions.