The rectangle packing problem is a combinatorial optimization problem, and is hard to solve it exactly in practical applications. In this paper, a tabu search heuristic is applied to the rectangle packing problem. First, each solution of the problem is represented by a pair of permutations of rectangles, and then the proposed method is described in detail, where the first admissible move strategy and a concept of stochastic tabu restrictions are employed. The experimental results are given to demonstrate the effectiveness of the proposed method.