Differential distributed space-time coding (DDSTC) technique has been considered for relay networks to provide both diversity gain and high throughput in the absence of channel state information. Conventional differential detection (CDD) or two-symbol non-coherent detection over slow-fading channels has been examined and shown to suffer 3–4 dB loss when compared to coherent detections. Moreover, it has also been shown that the performance of CDD severely degrades in fast-fading channels and an irreducible error floor exists at high signal-to-noise ratio region. To overcome the error floor experienced with fast-fading, a nearly optimal “multiple-symbol” differential detection (MSDD) is developed in this paper. The MSDD algorithm jointly processes a larger window of received signals for detection and significantly improves the performance of D-DSTC in fast-fading channels. The error performance of the MSDD algorithm is illustrated with simulation results under different fading scenarios.