Stories of flying people (or demi-gods or gods) go back all the way into pre-history. But in my experience, most or all of the early representations of super-human flight are either based on an item external to the user (such as a flying chariot or animal) or a more obvious, mechanical means of propulsion (such as natural or artificial wings). Magical levitation is also quite an old concept, but this generally involved simple hovering of a few feet above the ground, not weaving between the clouds.
But these days, a mainstay of popular culture is the power of superhuman flight, in which a person can propel themselves through the air at great speed without any obvious means of propulsion at all. Sometimes a cursory explanation is given (e.g. "it's self-directed telekinesis" or "their molecules can match the density of air"), but often it goes completely unexplained. They basically "just can." It's something that this character can do.
What is the earliest example of this kind of flight, one in which a humanoid character can hover, fly, rise and fall seemingly by thought alone? Did it develop immediately, debuting alongside a new character from their first appearance, or were there steps to its evolution (such as a character being able to hover at first, and then later being shown to actually fly, etc)?