A Large Deviation Principle (LDP) for the free energy of random Gibbs measures is proved in the form of a general LDP for random log-Laplace integrals. The principle is then applied to an extended version of the Random Energy Model (REM). The rate of exponential decay for the classical REM is stronger than the known concentration exponent, and probabilities of negative deviations are super-exponentially small.