In this paper, we propose a new design criterion and a new class of unitary signal constellations for differential space-time modulation for multiple-antenna systems over Rayleigh flat-fading channels with unknown fading coefficients. Extensive simulations show that the new codes have significantly better performance than existing codes. We have compared the performance of our codes with differential detection schemes using orthogonal design, Cayley differential codes, fixed-point-free group codes, and product of groups and for the same bit-error rate, our codes allow smaller signal-to-noise ratio (SNR) by as much as 10 dB. The design of the new codes is accomplished in a systematic way through the optimization of a performance index that closely describes the bit-error rate as a function of the SNR. The new performance index is computationally simple and we have derived analytical expressions for its gradient with respect to constellation parameters. Decoding of the proposed constellations is reduced to a set of one-dimensional closest point problems that we solve using parallel sphere decoder algorithms. This decoding strategy can also improve efficiency of existing codes.