Random scattering of light in transmission media has attracted a great deal of attention in the field of photonics over the past few decades. An optoelectronic oscillator (OEO) is a microwave photonic system offering unbeatable features for the generation of microwave oscillations with ultra-low phase noise. Here, we combine the unique features of random scattering and OEO technologies by proposing an OEO structure based on random distributed feedback. Thanks to the random distribution of Rayleigh scattering caused by inhomogeneities within the glass structure of the fiber, we demonstrate the generation of ultra-wideband (up to 40 GHz from DC) random microwave signals in an open cavity OEO. The generated signals enjoy random characteristics, and their frequencies are not limited by a fixed cavity length figure. The proposed device has potential in many fields such as random bit generation, radar systems, electronic interference and countermeasures, and telecommunications.