Phase transition is a concept borrowed from physics. It describes a situation where an abrupt change of behavior is observed in a system when an external condition is being modified. In this chapter, this abrupt change refers to the performance of a metaheuristic to solve an instance of a satisfaction problem (SAT), as the difficulty of the problem is increased. The chapter develops this idea in a well-defined mathematical framework, based on a population of randomly generated SAT problems. The probability that such a problem has a solution as a function of its difficulty is introduced. This probability, the distribution of the solutions in the search space, and the performance of the search methods all exhibit a phase transition as the ratio of the number of constraints to the number of variables in the SAT problem goes over a critical threshold.