We describe an ultra-stable, ultra-robust, straightforward and low-cost approach for the colorimetric detection of H2S with nanocrystalline cellulose (NCC) based on the reaction of H2S with lead acetate. The presence of NCC not only mediates the seed growth of a PbS/NCC complex, but also acts as a stabilizer protecting PbS from precipitation. This stable system is so robust that it can be used to quantitatively detect H2S even after two-year storage.