We present a novel solution approach to the container pre-marshalling problem using the A* and IDA* algorithms combined with several novel branching and symmetry breaking rules that significantly increases the number of pre-marshalling instances that can be solved to optimality. A* and IDA* are graph search algorithms that use heuristics combined with a complete graph search to find optimal solutions to problems. The container pre-marshalling problem is a key problem for container terminals seeking to reduce delays of inter-modal container transports. The goal of the container pre-marshalling problem is to find the minimal sequence of container movements to shuffle containers in a set of stacks such that the resulting stacks are arranged according to the time each container must leave the stacks. We evaluate our approach on three well-known datasets of pre-marshalling problem instances, solving over 500 previously unsolved instances to optimality, which is nearly twice as many instances as the current state-of-the-art method solves.