Embodiments for rebalancing distributed deduplication metadata by a processor. An input similarity unit of data and a corresponding input representative value are received on an ingesting processor. A corresponding deduplication metadata slice and owning processor are calculated for the input similarity unit. The input representative value and input digest values are sent to the owning processor. The owning processor is used to search for the input representative value in a corresponding deduplication metadata slice, and to forward the input representative value and input digest values to an additional processor, if the input representative value is not found by the owning processor and a rebalancing status of the owning processor is in-process. The additional processor is used to send a reply message to the owning processor that facilitates migration of the input representative value and corresponding input digest values to the owning processor, if the input representative value is found.