In an OFDM-based cooperative relay system, the arrival times and carrier frequency offsets (CFOs) of the signals from different relays are most likely different. Estimation of these timing offsets and CFOs is a crucial and challenging task. In this paper, a new preamble structure is designed, and an efficient time and frequency offset estimator is proposed for the OFDM-based cooperative system. The signals from different relays are separated using the low cross-correlated pseudo noise (PN) sequences. The coarse timing synchronization is accomplished using the time-domain symmetric conjugate of the preamble, and the fine timing synchronization is accomplished by segmented moving correlation using the good autocorrelation feature of the preamble in the time domain. The fractional frequency offset is estimated using the phase difference of the two duplicated training symbols, and the integral frequency offset is estimated by utilizing the low energy at null subcarriers and the good autocorrelation features of the preamble in the frequency domain. The analysis and the simulation results show that adopting the proposed preamble structure and synchronization algorithms, the destination can estimate not only the timing offsets from all relays but also the frequency offsets from all relays.