A new type of FeTiTaO6 ceramics with a high density was synthesized by the solid-state method. X-ray diffraction and scanning electron microscopy patterns indicate that the specimens exhibit a rutile structure and the mean particle size was about 200-300 nm. The heterovalent substitutions of Fe3+ and Ta5+ at Ti4+ site drive the incipient ferroelectric to the relaxor behavior, and a strong dispersion of the maximum dielectric permittivity appears around T-m, which shifts towards higher temperatures with the increasing frequency. The variation of T-m with frequency follows the Vogel-Fulcher relationship well, wherein E-a=0.068 eV, T-f=508 K, and f(0)=109 Hz. These results indicate that the nonperovskite-type FeTiTaO6 ceramic is a promising candidate for lead-free relaxor ferroelectrics in practical applications.