We examine the density of states of an Andreev billiard and show that any billiard with a finite upper cut-off in the path length distribution $P(s)$ will possess an energy gap on the scale of the Thouless energy. An exact quantum mechanical calculation for different Andreev billiards gives good agreement with the semi-classical predictions when the energy dependent phase shift for Andreev reflections is properly taken into account. Based on this new semi-classical Bohr-Sommerfeld approximation of the density of states, we derive a simple formula for the energy gap. We show that the energy gap, in units of Thouless energy, may exceed the value predicted earlier from random matrix theory for chaotic billiards.