Robustness is an important issue in the development of multi-bits watermarking algorithm. A new algorithm for robust multi-bits image watermarking based on Hidden Markov Model (HMM) in wavelet domain is proposed. The algorithm is characterized as follows: (1) the proposed blind detector based on vector HMM, which is employed to describe the statistics of wavelet coefficients, achieves significant improvements in performance compared to the conventional correlation detector; (2) an adaptive watermark embedding scheme is applied to achieve the low distortion according to the human visual system; (3) an optimal multi-bit watermark embedding strategy and a maximum-likelihood detection for tree structure of vector HMM are proposed through system robustness analysis. Simulation results show that relatively high capacity for watermark embedding in low frequency subbands of wavelet domain is achieved with the proposed algorithm, and high robust results are observed against Stirmark attacks, such as JPEG compress, adding noise, median cut and filter.