In this paper, joint methods of cell searching and Direction-of-Arrival (DoA) estimation for a mobile relay station with a uniform circular array are proposed. The proposed joint estimation method for the mobile relay station is robust even when there exist symbol timing offsets between the signals received from adjacent base stations. Also, the proposed joint estimation method can reduce computational complexity and processing time, compared with the case where cell searching and DoA estimation are performed separately. Performances of the proposed method are evaluated by computer simulation under Mobile WiMAX environment.