Watermarking is of vital importance for copyright protection and content authentication of images. With the development of compressive sensing, it has been successfully applied for watermarking with improved performance. Since an image can exhibit tree structure in wavelet domain, a new watermarking embedding and extraction method is proposed based on tree-structured Bayesian compressive sensing. The Markov Chain Monte Carlo (MCMC) method and the variational Bayesian (VB) analysis can be used for inference, respectively. Attacks to the watermarking, such as Gaussian noise, salt and pepper noise, Gaussian filtering, and JPEG compression, are given to evaluate the watermarking robustness with comparison to other reported reconstruction algorithms such as basis pursuit, orthogonal matching pursuit, Bayesian compressive sensing using relevance vector machine (RVM), and Bayesian compressive sensing with VB. Simulation results and comparisons show remarkable advantages of the tree-structured Bayesian compressive sensing for watermarking embedding and extraction.