A computer-implemented method for securely deduplicating data owned by multiple entities may include 1) identifying a first data segment to store on a third-party storage system, 2) identifying a client-specific database for fingerprints of deduplicated data segments stored on the third-party storage system, 3) identifying a third-party database for fingerprints of deduplicated data segments stored on the third-party storage system, 4) generating a fingerprint based on the first data segment, 5) determining that the fingerprint is not identified in the client-specific fingerprint database, 6) determining that the fingerprint is not identified in the third-party fingerprint database, 7) encrypting the first data segment with a third-party public encryption key, and then 8) transmitting the encrypted first data segment to the third-party storage system. Various other methods, systems, and computer-readable media are also disclosed.