Colossal permittivity (CP) (epsilon(r)=10(4)similar to 10(5)) is attained in (A(1/3)Nb(2/3))(x)Ti1-xO2 (A=Ba2+, Ca2+, Zn2+, Mg2+) ceramics. Here, (Ca1/3Nb2/3)(x)Ti1-xO2 material was studied as a typical example, and effects of Ca and Nb on their microstructure, dielectric properties and stability were studied. Both backscattering and elements mapping strongly confirmed the formation of secondary phases due to the addition of Ca and/or Nb. Secondary phases-induced by Ca cannot affect dielectric properties of the ceramics when low Ca and Nb contents were doped, while secondary phases formed by Ca and Nb strongly affected their dielectric properties in a high doping level. In particular, their dielectric properties can be well modified by the optimization of sintering temperatures. In addition, the (Ca1/3Nb2/3)(x)Ti1-xO2 ceramics with x=0.01 exhibited the optimum dielectric properties (epsilon(r)=130500 and tan =0.19). Electron-pinned defect-dipoles may be suitable to explain CP phenomenon of this work. We believed that this profound investigation can benefit the development of new TiO2 ceramics as a CP material.