Fault localization is an important and expensive activity in software debugging. Previous studies indicated that statistically-based fault-localization techniques are effective in prioritizing the possible faulty statements with relatively low computational complexity, but prior works on statistical analysis have not fully investigated the behavior state information of each program element.The objective of this paper is to propose an effective fault-localization approach based on the analysis of state dependence information between program elements.In this paper, state dependency is proposed to describe the control flow dependence between statements with particular states. A state dependency probabilistic model uses path profiles to analyze the state dependency information. Then, a fault-localization approach is proposed to locate faults by differentiating the state dependencies in passed and failed test cases.We evaluated the fault-localization effectiveness of our approach based on the experiments on Siemens programs and four UNIX programs. Furthermore, we compared our approach with current state-of-art fault-localization methods such as SOBER, Tarantula, and CP. The experimental results show that, our approach can locate more faults than the other methods in every range on Siemens programs, and the overall efficiency of our approach in the range of 10–30% of analyzed source code is higher than the other methods on UNIX programs.Our studies show that our approach consistently outperforms the other evaluated techniques in terms of effectiveness in fault localization on Siemens programs. Moreover, our approach is highly effective in fault localization even when very few test cases are available.