High-temperature relaxor ferroelectric behavior (T-m similar to 550 K) is reported for the rutile-based oxide, FeTiTaO6. Our investigations of the structure and dielectric properties of MTiTaO6 (M = Al, Cr, Fe) have revealed that all the oxides possess disordered rutile structure but only the iron member shows a strong relaxor ferroelectric effect. The new material is lead-free and it is based on the rutile structure, unlike the conventional relaxors which are mostly derived from the perovskite structure.