The relaxation processes of a wide variety of soft materials frequently contain one or more broad regions of power-law like or stretched exponential relaxation in time and frequency. Fractional constitutive equations have been shown to be excellent models for capturing the linear viscoelastic behavior of such materials, and their relaxation modulus can be quantitatively described very generally in terms of a Mittag-Leffler function. However, these fractional constitutive models cannot describe the nonlinear behavior of such power-law materials. We use the example of Xanthan gum to show how predictions of nonlinear viscometric properties, such as shear-thinning in the viscosity and in the first normal stress coefficient, can be quantitatively described in terms a nonlinear fractional constitutive model. We adopt an integral K-BKZ framework and suitably modify it for power-law materials exhibiting Mittag-Leffler type relaxation dynamics at small strains. Only one additional parameter is needed to predict nonlinear rheology, which is introduced through an experimentally measured damping function. Empirical rules such as the Cox-Merz rule and Gleissle mirror relations are frequently used to estimate the nonlinear response of complex fluids from linear rheological data. We use the fractional model framework to assess the performance of such heuristic rules and quantify the systematic offsets, or shift factors, that can be observed between experimental data and the predicted nonlinear response. We also demonstrate how an appropriate choice of fractional constitutive model and damping function results in a nonlinear viscoelastic constitutive model that predicts a flow curve identical to the elastic Herschel-Bulkley model. This new constitutive equation satisfies the Rutgers-Delaware rule, which is appropriate for yielding materials. This K-BKZ framework can be used to generate canonical three-element mechanical models that provide nonlinear viscoelastic generalizations of other empirical inelastic models such as the Cross model. In addition to describing nonlinear viscometric responses, we are also able to provide accurate expressions for the linear viscoelastic behavior of complex materials that exhibit strongly shear-thinning Cross-type or Carreau-type flow curves. The findings in this work provide a coherent and quantitative way of translating between the linear and nonlinear rheology of multiscale materials, using a constitutive modeling approach that involves only a few material parameters. (C) 2014 The Society of Rheology.