Methods, apparatus, and processor-readable storage media for estimating replication completion time using machine learning techniques are provided herein. An example computer-implemented method includes obtaining, from one or more data deduplication storage systems, data related to one or more historical replication operations; generating at least one curve fitting function by processing at least a portion of the obtained data using one or more machine learning techniques; generating an estimate for completion time of at least one unexecuted replication operation associated with at least one of the one or more data deduplication storage systems by processing input data from the at least one data deduplication storage system using the at least one curve fitting function; and performing one or more automated actions based at least in part on the generated estimate.