LaNb1-xMxO4+δ (M = W, Mo) which adopts a modulated tetragonal scheelite type structure exhibits enormous potential as an electrolyte material for solid oxide fuel cells. Here we report the solid-state synthesis of a series of W/Mo co-substituted samples with LaNb0.8WxMo0.2-xO4.1 (x = 0.00, 0.02, 0.04, 0.10, 0.16, 0.18, 0.20) which exhibited the highest total conductivity at x = 0.02 in the intermediate temperature range (2.37 × 10−3 S cm−1 at 665 °C in air). Powder X-ray diffraction patterns showed that the tetragonal phases were able to be stabilized at room temperature when x > 0.02. The phase diagram obtained from variable-temperature X-ray diffraction, indicated that the modulated structures could be maintained from room temperature to 900 °C when x ≥ 0.10. With the combination of electrochemical impedance spectroscopy measurements and Rietveld refinements from X-ray diffraction patterns, total conductivities of these materials were found to be proportional to the volume of the unit cells. It is also noted that the existence of modulated structures negatively impacts the total conductivities.