The container relocation problem (CRP) is concerned with clearing out a single yard-bay which contains a fixed number of containers each following a given pickup order so as to minimize the total number of relocations made during their retrieval process. In this work, we consider an extension of the CRP where containers are both received and retrieved at a single yard-bay named Dynamic Container Relocation Problem (DCRP). The arrival and departure sequences of containers are assumed to be known in advance. A tabu search based heuristic approach is proposed to solve the DCRP. Computational experiments are performed on an extensive set of randomly generated test instances from the literature. Our results show that the proposed algorithm is efficient and yields promising outcomes.