Proposed in this paper is a novel attribute reduction algorithm based on the attribute discernibility to re-duce the high computational complexity of the existing attribute reduction algorithms for incomplete decision tables.In the investigation, the external manifestation of condition attribute significance relative to the decision attribute inincomplete decision tables is analyzed, the attribute discernibility is defined, and the calculating method of dynamicupdate of attribute discernibility with the change of reduction subset is proposed. During the attribute reduction, thealgorithm continuously deletes the objects belonging to the positive domain or the consistent blocks having no effecton the positive domain calculation. Thus, the data scale and the time consumption decreases, and the attribute re-duction quickens. Theoretical analyses and simulation experiments demonstrate that the proposed attribute reductionalgorithm for incomplete decision tables is effective and is superior to the existing algorithms in terms of time com-plexity.