This work proposes a robust fault detection and isolation (FDI) scheme for linear discrete-time systems subject to faults, bounded additive disturbances and norm-bounded structured uncertainties. FDI is achieved by computing, on-line, upper and lower bounds on the fault signal such that a fault is regarded as having occurred when its upper bound is smaller than zero or lower bound is larger than zero. Linear Matrix Inequality (LMI) optimization techniques are used to obtain the bounds. Furthermore, a subsequent-state-estimation technique, together with an estimation horizon update procedure, is proposed, which allows the on-line FDI process to be repeated in a moving horizon procedure. The approach is also extended to solve the fault detection (FD) problem of obtaining lower bounds on the total fault signal energy within the estimation horizon. The scheme gives the best estimates of the fault signals given the information available and is sufficiently flexible to incorporate other information that may be available, such as bounds on the disturbance energy. Thus our scheme is immune to false alarms if the system and disturbance are within the uncertainty description. Moreover, we propose a new robustness result to obtain the bounds, which is an extension of current techniques for handling model uncertainties. Finally, the approach is verified using two numerical examples. (C) 2013 Elsevier Ltd. All rights reserved.