The generation of a two-octave supercontinuum from the visible to mid-infrared (700–2800 nm) in a non-silica graded-index multimode fiber is reported. The fiber design is based on a nanostructured core comprised of two types of drawn lead-bismuth-gallate glass rods with different refractive indices. This yields an effective parabolic index profile and ten times increased nonlinearity when compared to silica fibers. Using femtosecond pulse pumping at wavelengths in both normal and anomalous dispersion regimes, a detailed study is carried out into the supercontinuum generating mechanisms and instabilities seeded by periodic self-imaging. Significantly, suitable injection conditions in the high power regime are found to result in the output beam profile showing clear signatures of beam self-cleaning from nonlinear mode mixing. Experimental observations are interpreted using spatio-temporal 3+1D numerical simulations of the generalized nonlinear Schrödinger equation, and simulated spectra are in excellent agreement with experiment over the full two-octave spectral bandwidth. Experimental comparison with the generation of supercontinuum in a silica graded-index multimode fiber shows that the enhanced nonlinear refractive index of the lead-bismuth-gallate fiber yields a spectrum with a significantly larger bandwidth. These results demonstrate a new pathway towards the generation of bright, ultrabroadband light sources in the mid-infrared.