Energy-efficient, reliable and scalable machine-to-machine (M2M) communications is the key technical enabler of Internet-of-Things (IoT) networks. Furthermore, as the number of populated devices is constantly increasing, self-sustaining or energy-autonomous IoT nodes are a promising prospect receiving increasing interest. In this paper, the feasibility and fundamental limits of energy harvesting based M2M communication systems are studied and presented. The derived theoretical bounds are effectively based on the Shannon theorem, combined with selected propagation loss models, assumed link nonidealities, as well as the given energy harvesting and storage capabilities. Fundamental limits and available operational time of the communicating nodes are derived and analyzed, together with extensive numerical results evaluated in different practical scenarios for low power sensor type communication applications.