Finding the best signal constellation for different communication channels is one of the fundamental problems in digital communication. This problem has been studied widely from different angles and many methods have been proposed for designing good practical signal constellations. There has been a rejuvenated interest in designing good constellations during last decade, in part due to the advent of novel optimization techniques. Nevertheless, most of the recent work, similar to the older work in this area, aims to optimize the constellation within a presumed structure (such as points lying on concentric rings). In this paper, we develop a different approach: we aim to optimize constellations based on a Chernoff bound on the probability of error in the versatile Nakagami-m fading channel. We derive two general bounds on the symbol error rate and bit error rate performance of orthogonal transmission in a Nakagami-m fading channel for single-input single-output and orthogonal space-time block codes and we show that a substantial improvement in the error probability is achieved with the novel constellations that are optimized using these bounds.