Brains are usually described as input/output systems: they transform sensory input into motor output. However, the motor output of brains (behavior) is notoriously variable, even under identical sensory conditions. The question of whether this behavioral variability merely reflects residual deviations due to extrinsic random noise in such otherwise deterministic systems or an intrinsic, adaptive indeterminacy trait is central for the basic understanding of brain function. Instead of random noise, we find a fractal order (resembling Lévy flights) in the temporal structure of spontaneous flight maneuvers in tethered Drosophila fruit flies. Lévy-like probabilistic behavior patterns are evolutionarily conserved, suggesting a general neural mechanism underlying spontaneous behavior. Drosophila can produce these patterns endogenously, without any external cues. The fly's behavior is controlled by brain circuits which operate as a nonlinear system with unstable dynamics far from equilibrium. These findings suggest that both general models of brain function and autonomous agents ought to include biologically relevant nonlinear, endogenous behavior-initiating mechanisms if they strive to realistically simulate biological brains or out-compete other agents.