Bit-interleaved coded modulation (BICM) transceivers often use equally spaced constellations and a random interleaver. In this paper, we propose a new BICM design, which considers hierarchical (nonequally spaced) constellations, a bit-level multiplexer, and multiple interleavers. It is shown that this new scheme increases the degrees of freedom that can be exploited in order to improve its performance. Analytical bounds on the bit error rate (BER) of the system in terms of the constellation parameters and the multiplexing rules are developed for the additive white Gaussian Noise (AWGN) and Nakagami-m fading channels. These bounds are then used to design the BICM transceiver. Numerical results show that, compared to conventional BICM designs, and for a target BER of 10-6, gains up to 3 dB in the AWGN channel are obtained. For fading channels, the gains depend on the fading parameter, and reach 2 dB for a target BER of 10-7 and m = 5.