A novel two-stage frequency domain channel estimation method especially suitable for the estimation of long channels such as ultra wide band channels is proposed. The proposed method can efficiently use the sequences with closed form analytical expressions such as the Legendre sequences. (The suggested method does not require a computationally intense search for good training sequences which is infeasible for long training sequences.) The method is shown to present a minor improvement in the total estimation error variance when compared with the conventional single stage frequency domain channel estimation. In addition, the proposed method has a very efficient time domain implementation requiring at most 2N multiplications, where N is the training sequence length, in comparison to O(N log N) multiplications required for the conventional method.