Most existing space-time coding schemes assume time-invariant fading channels and offer antenna diversity gains relying on accurate channel estimates at the receiver. Based on a diagonal unitary matrix group, a novel double differential space-time block coding approach is derived in this paper for time-selective fading channels. Without estimating the channels at the receiver, information symbols are recovered with antenna diversity gains regardless of frequency offsets. The resulting transceiver has very low complexity and is applicable to an arbitrary number of transmit and receive antennas. Approximately optimal space-time codes are also designed to minimize bit error rate. System performance is evaluated both analytically and with simulations.