For example, an EDMG STA may be configured to generate a plurality of spatial streams of an EDMG PPDU; map the plurality of spatial streams to a respective plurality of pairs of space-time streams according to an STBC scheme by mapping a first data sequence of a spatial stream to a first symbol in an odd numbered space-time stream, mapping a second data sequence of the spatial stream to a second symbol in the odd numbered space-time stream, mapping a sign inverted complex conjugate of the second data sequence to a first symbol in an even numbered space-time stream, and mapping a complex conjugate of the first data sequence to a second symbol in the even numbered space-time stream; and transmit a transmission comprising the plurality of pairs of space-time streams over a channel bandwidth in a frequency band above 45 Gigahertz (GHz).