The Mg2+/Ta5+ codoped rutile TiO2 ceramic with a nominal composition (Mg1/3Ta2/3)0.01Ti0.99O2 was synthesized using a conventional solid-state reaction method and sintered at 1400 °C for 2 h. The pure phase of the rutile TiO2 structure with a highly dense microstructure was obtained. A high dielectric permittivity (2.9 × 104 at 103 Hz) with a low loss tangent (<0.025) was achieved in the as-sintered ceramic. After removing the outer surface, the dielectric permittivity of the polished ceramic increased from 2.9 × 104 to 6.0 × 104, while the loss tangent also increased (~0.11). The dielectric permittivity and loss tangent could be recovered to the initial value of the as-sintered ceramic by annealing the polished ceramic in air. Notably, in the temperature range of −60–200 °C, the dielectric permittivity (103 Hz) of the annealed ceramic was slightly dependent (<±4.4%), while the loss tangent was very low (0.015–0.036). The giant dielectric properties were likely contributed by the insulating grain boundaries and insulative surface layer effects.