Complex impedance and dielectric permittivity of titania-polypyrrole nanocomposites have been investigated as a function of frequency and temperature at different compositions. A very large dielectric constant of about 13,000 at room temperature has been observed. The colossal dielectric constant is mainly dominated by interfacial polarization due to Maxwell-Wagner relaxation effect. Two completely separate groups of dielectric relaxation have been observed. The low frequency dielectric relaxation arises from surface defect states of titania nanoparticles. The broad peak at high frequency region is attributed to Maxwell-Wagner type polarization originating from the inhomogeneous property of nanocomposite. An abrupt change in grain boundary conductivity and dielectric relaxation associated with titania was observed at around 150 K. Anomalous behavior in conductivity and dielectric relaxation is qualitatively explained by band tail structure of titania nanoparticle.