Large fergusonite-type (ABO4, A=Ce, B=Nb) oxide crystals, a prototype electrolyte composition for solid oxide fuel cells (SOFC), were prepared for the first time in a floating zone mirror furnace under air or argon atmospheres. While CeNbO4 grown in air contained CeNbO4.08 as a minor impurity that compromised structural analysis, the argon atmosphere yielded a single phase crystal of monoclinic CeNbO4, as confirmed by selected area electron diffraction, powder and single crystal X-ray diffraction. The structure was determined in the standard space group setting C12/c1 (No. 15), rather than the commonly adopted I12/a1. AC impedance spectroscopy conducted under argon found that stoichiometric CeNbO4 single crystals showed lower conductivity compared to CeNbO4+δ confirming interstitial oxygen can penetrate through fergusonite and is responsible for the higher conductivity associated with these oxides.