The development of portable and wearable electronics requiring only few tens of microwatts to operate fosters the search for low power energy sources. Moreover, the fast-growing demand for new sustainable energy has raised the interest in energy harvesters able to convert mechanical energy into electrical power. Triboelectric nanogenerators (TENGs) can provide such green power supply. Recent developments in TENGs technology show that they can be used in different applications ranging from wearable self-powered sensors to wind and sea wave energy harvesting. In spite of the wide number of TENGs developed so far, an in depth understanding of their working principle is still missing. In this work, we highlight the fundamental role played by the interface between the triboelectric material and the electrode collector in contributing to the TENG's power generation. We show that by simply replacing the'standard'gold electrodes with flexible few layer graphene electrodes in TENGs operating in vertical contact mode, a 26-fold increase in power density is achieved. Here, we elucidate the main mechanism at the base of such boost in power output, describing guidelines for the combination of electrode and triboelectric materials to optimize the mechanical energy conversion efficiency in TENGs.