IEEE 802.16j standard defines Relay Station (RS) to enhance network throughput. Deploying RSs within the serving area of the Base Station (BS) could increase network throughput but raise the hardware cost problem. This paper presents a deployment algorithm for IEEE 802.16j network. According to the history traffic of internet usage, the proposed algorithm deploys as few as possible RSs at suitable locations such that the traffic requirement of each subarea can be satisfied. The proposed relay deployment algorithm mainly consists of three phases. The first phase aims to construct several promising zones where a RS deployed in each zone can improve the transmission rate from mobile station to BS. The second phase further combines several zones into a bigger one aiming at reducing the number of deployed RSs. The last phase selects the relay zones from the promising zones and deploys one RS in each relay zone. Simulation results show that our proposed algorithm can deploy the RSs at the most appropriate locations and hence efficiently reduce transmission delay and save the hardware cost.