In this paper, we study chance constrained mixed integer program with consideration of recourse decisions and their incurred cost, developed on a finite discrete scenario set. Through studying a non-traditional bilinear mixed integer formulation, we derive its linear counterparts and show that they could be stronger than existing linear formulations. We also develop a variant of Jensen’s inequality that extends the one for stochastic program. To solve this challenging problem, we present a variant of Benders decomposition method in bilinear form, which actually provides an easy-to-use algorithm framework to integrate existing improvement techniques, along with a few enhancement strategies based on the structure of chance constrained program. Computational study shows that the presented Benders decomposition method outperforms a commercial solver by an order of magnitude on solving chance constrained program or detecting its infeasibility.