The probabilistic combinatorial optimization problem (PCOP) is a generic name of a specific family of combinatorial optimization problems whose common characteristic is the explicit inclusion of the probabilistic elements in the problem definitions. The main contribution of the paper is to introduce polyhedral combinatorics to the area of PCOPs. Some concepts of polyhedral theory are generalized to the PCOPs. We also prove some theorems which give the general methodology for deriving the valid inequalities. Based on these basic results we can derive lower bounds for the probabilistic variations of several well-known and practically important combinatorial optimization problems.