In this study, we consider a real-life export container storage problem at an important container terminal in the Port of Izmir, Turkey. Currently, the container storage decisions at the port are taken by operators manually, which leads to continuous unnecessary re-handling movements of the containers. High transportation costs, waste of time, and inefficient capacity utilization in the container storage area are the consequences of non-optimal decisions. The main goal of this study is to minimize the transportation costs and the number of re-handling moves while storing the export containers at the terminal yard. We formulate the problem in two stages. While the first stage assigns the containers of the same vessel to a group of yard bays via an optimization model, the second stage decides on the exact location of each container with the help of an efficient heuristic approach. The experimental results with real data are presented and discussed.