We investigate the use of parabolic interpolation in data hiding and propose a novel data hiding algorithm with high capacity based on interpolated image. Specifically, the proposed algorithm creates an interpolated image from input image by parabolic interpolation, and embeds secret bits into interpolated pixels in terms of the relation between the interpolated value and the mean value. Ten standard benchmark images are taken as test images for validating efficiency of our algorithm. The results illustrate that our algorithm has better performances than some popular data hiding methods in embedding capacity and visual quality with respect to PSNR and SSIM.