Air bubbles rising through an aqueous medium have been studied extensively and are routinely used for the separation of particulates via froth flotation, a key step in many industrial processes. Oil-coated bubbles can be more effective for separating hydrophilic particles with low affinity for the air-water interface, but the rise dynamics of oil-coated bubbles has not yet been explored. In the present work, we report the first systematic study of the shape and rise trajectory of bubbles engulfed in a layer of oil. Results from direct observation of the coated bubbles with a high-speed camera are compared to computer simulations and confirm a pronounced effect of the oil coat on the bubble dynamics. We consistently find that the oil-coated bubbles display a more spherical shape and straighter trajectory, yet slower rise than uncoated bubbles of comparable size. These characteristics may provide practical benefits for flotation separations with oil-coated bubbles.