Providing a complete and accurate domain model for an agent situated in a complex environment can be an extremely dJfflcult task. Actions may have different effects depending on the context in which they are taken, and actions may or may not induce their intended effects, with the probability of success again depending on context. In addition, the contexts and probabilities that govern the effects and success of actions may change over time. We present an algorithm for automatically learning planning operators with context-dependent and probabilistic effects in environments where exogenous events change the state of the world. Our approach assumes that a situated agent has knowledge of the types of actions that it can take, but initially knows nothing of the contexts in which an action produces change in the environment, nor what that change is likely to be. The algorithm accepts as input a history of state descriptions observed by an agent while taking actions in its domain, and produces as output descriptions of planning operators that capture structure in the agent’s interactions with its environment. We present results for a sample domain showing that the computational requirements of our algorithm scale approximately linearly with the size of the agent’s state vector, and that the algorithm successfully locates operators that capture true structure and avoids those that incorporate noise.