We have prepared different compositions in the Gd2−yLayZr2O7 solid solution by mechanically milling stoichiometric mixtures of the corresponding oxides. Irrespective of their lanthanum content, as-prepared powder samples consist of single-phase anion-deficient fluorite materials, although the long-range ordering of cations and anion vacancies characteristic of pyrochlores was observed for y≥0.4 after post-milling thermal treatments at 1200 °C. Ionic conductivity was found to be thermally activated and almost independent of La content for 0≤y≤1, since the pre-exponential factor decreases as structural ordering increases; however, there is a concomitant decrease of the activation energy Edc for oxide-ion diffusion, from Edc = 1.13 ± 0.02 eV for the anion-deficient fluorite Gd2Zr2O7 to Edc = 0.85 ± 0.03 eV for the partially ordered pyrochlore-type Gd1.2La0.8Zr2O7. Electrical conductivity relaxation is well described by a Kohlrausch–Williams–Watts (KWW) function of the form Φ = exp(−(t/τ)1−n), where the fractional exponent n decreases as the La content (ordering) increases. These results are explained in terms of weaker ion–ion interactions in the better ordered structure and highlight the importance of structural ordering/disordering in determining the dynamics of mobile oxygen ions.