This paper investigates wave propagation of size-dependent functionally graded (FG) nanobeams resting on elastic foundation subjected to axial magnetic field based on the nonlocal strain gradient theory and Euler-Bernoulli beam model by using an analytical approach. The nonlocal beam model has a length scale parameter and captures the size influences. Material properties are spatially graded according to sigmoid distribution. Aderivation of the governing equations for the wave propagation analysis of nanoscale S-FGM beams is conducted. Then, the dispersion relations between wave frequency and phase velocity with the wave number is investigated. It is found that wave propagation characteristics of nonlocal S-FGM beams are influenced by various parameters including length scale parameter, material graduation, elastic foundation parameters and magnetic field intensity.