Core-shell structures of oxide nanoparticles having a high dielectric constant, and organic shells with large breakdown field are attractive candidates for large electrical energy storage applications. A high growth temperature, however, is required to obtain the dielectric oxide nanoparticles, which affects the process of core-shell formation and also leads to poor control of size, shape, and size-distribution. In this communication, we report a new synthetic process to grow core-shell nanoparticles by means of an experimental method that can be easily adapted to synthesize core-shell structures from a variety of inorganic-organic or inorganic-inorganic materials. Monodisperse and spherical TiO2 nanoparticles were produced at room temperature as a collimated cluster beam in the gas phase using a cluster-deposition source and subsequently coated with uniform paraffin nanoshells using in situ thermal evaporation, prior to deposition on substrates for further characterization and device processing. The paraffin nanoshells prevent the TiO2 nanoparticles from contacting each other and also act as a matrix in which the volume fraction of TiO2 nanoparticles was varied by controlling the thickness of the nanoshells. Parallel-plate capacitors were fabricated using dielectric core-shell nanoparticles having different shell thicknesses. With respect to the bulk paraffin, the effective dielectric constant of TiO2-paraffin core-shell nanoparticles is greatly enhanced with a decrease in the shell thickness. The capacitors show a minimum dielectric dispersion and low dielectric losses in the frequency range of 100 Hz-1 MHz, which are highly desirable for exploiting these core-shell nanoparticles for potential applications.