(Cr,Nb)TiO2 (CN-T) and (Sc,Nb)TiO2 (SN-T) ceramics were prepared via a solid state reaction process. A single phase of rutile TiO2 was confirmed by X-ray diffraction (XRD). Dielectric properties were investigated over frequency range from 40Hz to 10MHz and temperature range from -70C to 220C. The ceramics showed high permittivities (>1000) with low dielectric losses and frequency-stablity. The behaviors of colossal permittivity can be explained by electron-pinned defect-dipoles, interfacial polarization and polaron hopping polarization.