An extensible fingerprint comprised of an ordered list of fingerprints generated by applying each of a plurality of distinct fingerprinting functions to the content of a data item. The extensible fingerprint can be extended by using a new fingerprinting function to compute a new fingerprint and adding the new fingerprint to the list so that the old extensible fingerprint of a data item is used as a prefix of the new extensible fingerprint for that data item. Thus, the fingerprint can be incrementally extended over time. A content-addressed storage system uses extensible fingerprints as addresses and can also change over time.