Nikki and Paulo murdered Howard L. Zukerman to steal his diamonds worth $8 million dollars. Following the murder, they broke into his safe and took them from a black pouch inside the innermost of a set of Matryoshka dolls. They planned to flee to Sydney with the diamonds via Oceanic Flight 815.
Following the crash, the two searched for the bag of diamonds. Nikki followed a tip from Kate about where she'd found the Halliburton case, and Paulo found the bag in the bottom of the waterfall. He hid the discovery and retrieved the doll and bag later. He hid them in the Pearl's toilet tank.
Miles, after robbing Nikki and Paulo's grave. ("Dr. Linus")
Once Locke and Eko discovered the Pearl, Paulo removed the diamonds and kept them on his person. Nikki discovered that he had them, paralyzed him with a Medusa spider, and retrieved the diamonds from his pants. Spiders bit her next, and she quickly buried the diamonds before running back to camp. Sawyer retrieved the diamonds and gave them to Sun when confronted with his acts. Sun gave them back, and Sawyer buried them with Nikki and Paulo. ("Exposé")