Nano-scaling of electrode materials is often used in battery applications to enhance performance, particularly relating to rate capability. However, for the high-voltage spinel LiNi0.5Mn1.5O4 conflicting results have been reported on the benefits of nano-scaling. In this study, we present first-principles calculations to investigate the effect of nano-scaling on LiNi0.5Mn1.5O4, specifically focusing on the roles and coupling between surface stability, cation ordering and phase behavior. We calculate and compare the surface energy for the low index facets (100), (110), and (111), and find that the most stable facet is dependent on the cation ordering at the surface layer. In this context, we predict a spontaneous surface reconstruction in the cation-ordered structure which leads to a deviation from the perfect surface cation ordering and results in an enhanced accessibility to solid solution behavior as a function of Li content. Our results imply that nano-scaling will be more beneficial for the cation-ordered structure, as compared to the disordered structure where the solid solution region is already intrinsically accessible for a broad range of Li concentrations.