Dissipative solitons relying on the double balance between nonlinear and linear effects as well as cavity loss and gain have attracted increasing attention in recent years, since they give rise to novel operating states of various dissipative nonlinear systems. An optoelectronic oscillator (OEO) is a dissipative nonlinear microwave photonic system with a high quality factor that has been widely investigated for generating ultra-low noise single-frequency microwave signals. Here, we report a novel operating state of an OEO related to dissipative solitons, i.e., spontaneous frequency hopping related to the formation of dissipative microwave photonic solitons. In this operating state, dissipative microwave photonic solitons occur due to the double balance between nonlinear gain saturation and linear filtering as well as cavity loss and gain in the OEO cavity, creating spontaneous frequency-hopping microwave signals. The generation of wideband tunable frequency-hopping microwave signals with a fast frequency-hopping speed up to tens of nanoseconds is observed in the experiment, together with the corresponding soliton sequences. This work reveals a novel mechanism between the interaction of nonlinear and linear effects in an OEO cavity, extends the suitability and potential applications of solitons, and paves the way for a new class of soliton microwave photonic systems for the generation, processing, and control of microwave and RF signals.