We investigate the decay of entanglement, due to decoherence, of multi-qubit systems that are initially prepared in highly (in some cases maximally) entangled states. We assume that during the decoherence processes each qubit of the system interacts with its own, independent environment. We determine, for systems with a small number of qubits and for various decoherence channels, the initial states exhibiting the most robust entanglement. We also consider a restricted version of this robustness optimization problem, only involving states equivalent under local unitary transformations to the |GHZ> state.