In this paper, cell searching and direction-of-arrival (DoA) estimation methods are proposed for mobile relay stations with a uniform linear arrays in OFDM-based cellular systems. The proposed methods can improve the performance of cell searching and DoA estimation, even when there exist symbol timing offsets among the signals received from adjacent base stations and Doppler frequency shifts caused by the movement of the mobile relay station. The performances and computational complexities of the proposed cell searching and DoA estimation methods are evaluated by computer simulation under a mobile WiMAX environment.