Single phase La1-xGdxNb0.9Mo0.1O4.05 (x=0, 0.20, 0.40, 0.50, 0.60, 0.80 and 1.00) has been synthesized by a solid state reaction route. The crystal structures of all samples were investigated by high temperature X-ray diffraction. Both LaNb0.9Mo0.1O4.05 and La0.8Gd0.2Nb0.9Mo0.1O4.05 were found to possess modulated crystal structures at room temperature. The electrochemical performance of all samples was investigated by electrochemical impedance spectroscopy. LaNb0.9Mo0.1O4.05 exhibited the highest total conductivity of 1.52 × 10−2 Scm−1 at 900 °C in air; however, at intermediate temperature range, the conductivity of La0.8Gd0.2Nb0.9Mo0.1O4.05 was higher than LaNb0.9Mo0.1O4.05. The reason for these phenomena could be related to the influence of the negative effects of a modulated structure on electrochemical performance and both Gd and Mo dopants on the stability of the sample, which was investigated using the Bond Valence Sum approach.