Fast convergence of the adaptive filter in an acoustic echo cancellation based hands-free communication system is desirable as it implies more periods of possible full-duplex communication. This paper presents a normalized least mean square (NLMS)-based algorithm, targeted for acoustic echo cancellation based units equipped with large external memory. The proposed algorithm utilizes unused processing resources in periods of silence, thus no extra complexity as compared with the conventional NLMS algorithm is required. The improvements obtained by the proposed algorithm are verified through simulated, as well as through real acoustic systems.