This paper presents a novel chaos-based self-embedding secure watermarking algorithm based on the chaotic pseudorandom ness and sensitivity to initial value of chaotic map. In the proposed approach, the real-valued chaotic sequence, which is generated by the given initial value as secret key, is used to produce the ordered indices as the watermark embedding positions. The proposed algorithm has a larger key space than the existing self-embedding watermarking algorithms due to its watermark embedding positions being randomly selected by the secret key. Furthermore, the problem, how to locate the tampered image block in the self-embedding watermarking algorithm has been solved successfully. Theoretical analysis and simulation results show that our scheme not only improves the abilities of tamper localization, but also has better security against many attacks, including the vector quantization and synchronous counterfeiting attacks.