In this paper, a novel data-hiding technique based on the Fibonacci representation of digital images is presented. A generalization of the classical Least Significant Bit (LSB) embedding method is performed. The Fibonacci representation of grey level images requires 12 bit planes instead of the usual 8 planes of binary representation. Experimental results show that, such a redundant scheme outperforms the classical LSB method resulting in marked images having less perceptual distortion even if different planes from the lowest bit plane are selected for embedding. The computational cost of the embedding scheme is compatible with the classical LSB data hiding scheme.