This paper proposes a method of systematically generating the failure criteria of truss structures by using Matrix Method. The resulting criterion for a statically determinate truss is simple and its failure probability is easily evaluated. In case of a statically indeterminate truss, however, there are many possible modes or paths to complete failure of the structure and it is impossible in practice to generate all of them. Hence, the failure probability is estimated by evaluating its lower and upper bounds. The lower bound is evaluated by selecting the dominant modes of failure and calculating their probabilities. The upper bound is evaluated by assuming that the redundant truss behaves itself like a statically determinate truss, i.e., the structure fails if any one member is subject to failure. Numerical examples are provided to demonstrate the applicability of the propsed methods.