In this paper, we consider the following form of temporal abduction: given a domain theory where each explanatory formula is augmented with a set of temporal constraints on the atoms occurring in the formula, and given a set of observed atoms, with associated temporal constraints, the goal is the generation of a temporally consistent abductive explanation of the observations. Temporal abduction is the basis of many problem solving activities such as temporal diagnosis or reasoning about actions and events. This paper presents an efficient nondeterministic algorithm for temporal abduction which exploits the STP framework [8] in order to represent temporal information. In particular, we exploited some properties of STP, proved in