This paper presents a novel performance evaluation framework for energy harvesting communications. As the harvested energy may not always be at the required levels in the transmitter’s battery, possible energy outage may hinder the transmission, especially in weak channel conditions. Herein, we analyze the performance of an energy harvesting communication link by allowing a certain level of energy outage to occur. Such operation is challenging, given that the energy coming into the battery from an uncontrollable source, e.g., solar energy, does not relate to the channel conditions and quality-of-service (QoS) requirement, whereas energy going out of the battery is directly dependent on both. Hence, the incoming energy and outgoing energy become independent of each other. Knowing the exact level of energy that is accumulated in the battery is therefore challenging. To deal with these challenges, a probabilistic energy-outage approach and a virtual battery queuing model are proposed and used to develop the target performance evaluation framework while leveraging the large deviation principle theorem. The derived energy-outage probability of the communication system relates the system parameters, namely, QoS component, channel conditions, and harvested energy. Numerical results are presented to confirm the analytical findings and discuss the performance of energy harvesting based communication with tolerable energy-outage as a function of the system parameters.