The properties of CaCu3.1Ti4O12.1 [CC3.1TO] ceramics with the addition of Al2O3 nanoparticles, prepared via a solid-state reaction technique, were investigated. The nanoparticle additive was found to inhibit grain growth with the average grain size decreasing from approximately 7.5 μm for CC3.1TO to approximately 2.0 μm for the unmodified samples, while the Knoop hardness value was found to improve with a maximum value of 9.8 GPa for the 1 vol.% Al2O3 sample. A very high dielectric constant > 60,000 with a low loss tangent (approximately 0.09) was observed for the 0.5 vol.% Al2O3 sample at 1 kHz and at room temperature. These data suggest that nanocomposites have a great potential for dielectric applications.