The rectilinear block packing problem involves packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90° or 270°. This problem is relevant for many applications, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristic algorithms for rectilinear block packing. The proposed algorithms are tested on a series of instances that are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances.