The interface between the polymer and nanoparticle has a vital role in determining the overall dielectric properties of a dielectric polymer nanocomposite. In this study, a novel dielectric nanocomposite containing a high permittivity polymer, cyanoethylated cellulose (CRS) and TiO2 nanoparticles surface modified by hydrogen plasma treatments was successfully prepared with different weight percentages (10%, 20% and 30%) of hydrogenated TiO2. Internal structure of H plasma treated TiO2 nanoparticles (H-TiO2) and the intermolecular interactions and morphology within the polymer nanocomposites were analysed. H-TiO2/CRS thin films on SiO2/Si wafers were used to form metal-insulator-metal (MIM) type capacitors. Capacitances and loss factors in the frequency range of 1 kHz to 1 MHz were measured. At 1 kHz H-TiO2/CRS nanocomposites exhibited ultra-high dielectric constants of 80, 118 and 131 for nanocomposites with 10%, 20% and 30% weight of hydrogenated TiO2 respectively, significantly higher than values of pure CRS (21) and TiO2 (41). Furthermore, all three H-TiO2 /CRS nanocomposites show a loss factor <0.3 at 1 kHz and low leakage current densities (10-6 A cm-2-10-7 A cm-2). Leakage was studied using conductive atomic force microscopy (C-AFM) and it was observed that the leakage is associated with H-TiO2 nanoparticles embedded in the CRS polymer matrix. Although, modified interface slightly reduces energy densities compared to pristine TiO2/CRS system, the capacitance values for H-TiO2/CRS-in the voltage range of -2 V to 2 V are very stable. Whilst H-TiO2/CRS possesses ultra-high dielectric constants (>100), this study reveals that the polymer nanoparticle interface has a potential influence on dielectric behaviour of the composite.