We present the analysis of the first NuSTAR observations ($sim 220$ ks), simultaneous with the last SUZAKU observations ($sim 50$ ks), of the active galactic nucleus of the bright Seyfert 1 galaxy Mrk 509. The time-averaged spectrum in the $1-79$ keV X-ray band is dominated by a power-law continuum ($Gammasim 1.8-1.9$), a strong soft excess around 1 keV, and signatures of X-ray reflection in the form of Fe K emission ($sim 6.4$ keV), an Fe K absorption edge ($sim 7.1$ keV), and a Compton hump due to electron scattering ($sim 20-30$ keV). We show that these data can be described by two very different prescriptions for the soft excess: a warm ($kTsim 0.5-1$ keV) and optically thick ($tausim10-20$) Comptonizing corona, or a relativistically blurred ionized reflection spectrum from the inner regions of the accretion disk. While these two scenarios cannot be distinguished based on their fit statistics, we argue that the parameters required by the warm corona model are physically incompatible with the conditions of standard coronae. Detailed photoionization calculations show that even in the most favorable conditions, the warm corona should produce strong absorption in the observed spectrum. On the other hand, while the relativistic reflection model provides a satisfactory description of the data, it also requires extreme parameters, such as maximum black hole spin, a very low and compact hot corona, and a very high density for the inner accretion disk. Deeper observations of this source are thus necessary to confirm the presence of relativistic reflection, and to further understand the nature of its soft excess.