We present a formalism for encoding the logical basis of a qubit into subspaces of multiple physical levels. The need for this multilevel encoding arises naturally in situations where the speed of quantum operations exceeds the limits imposed by the addressability of individual energy levels of the qubit physical system. A basic feature of the multilevel encoding formalism is the logical equivalence of different physical states and correspondingly, of different physical transformations. This logical equivalence is a source of a significant flexibility in designing logical operations, while the multilevel structure inherently accommodates fast and intense broadband controls thereby facilitating faster quantum operations. Another important practical advantage of multilevel encoding is the ability to maintain full quantum-computational fidelity in the presence of mixing and decoherence within encoding subspaces. The formalism is developed in detail for single-qubit operations and generalized for multiple qubits. As an illustrative example, we perform a simulation of closed-loop optimal control of single-qubit operations for a model multilevel system, and subsequently apply these operations at finite temperatures to investigate the effect of decoherence on operational fidelity.