Ah sorry ShinyUmbreon, apparently the earliest place you can capture Natu is the small patch of grass in Ruins of Alph which you need surf and strength to access. If you can wait that long for a flying type you can find it from 18-24. Just beware that anything under 23 knows teleport. It appears all day with a 90% chance.
If you don't want to wait that long I think there are other really decent early flying types out there you can pick from .