A fault-tolerant observer design methodology is proposed. The aim is to guarantee a minimum level of closed-loop performance under all possible sensor fault combinations while optimizing performance under the nominal, fault-free condition. A novel approach is proposed to tackle the combinatorial nature of the problem, which is computationally intractable even for a moderate number of sensors, by recasting the problem as a robust performance problem, where the uncertainty set is composed of all combinations of a set of binary variables. A procedure based on an elimination lemma and an extension of a semidefinite relaxation procedure for binary variables is then used to derive sufficient conditions (necessary and sufficient in the case of one binary variable) for the solution of the problem which significantly reduces the number of matrix inequalities needed to solve the problem. The procedure is illustrated by considering a fault-tolerant observer switching scheme in which the observer outputs track the actual sensor fault condition. A numerical example from an electric power application is presented to illustrate the effectiveness of the design.