Since the first exfoliation in 2004, graphene has been widely researched in many fields of materials engineering due to its highly appealing properties. Recently, graphene-based composites have attracted increasing attention for electrochemical energy storage by combining the merits of graphene and other electrochemical materials to achieve superior electrochemical performances. In this review, we start with the properties and production methods for graphene, summarize the recent research progress on graphene-based composites for electrochemical energy storage from the structural and interfacial engineering viewpoints, and underscore the significance of the dimensionality and compound interface characteristics in the rational construction and design of these composites. We also discuss recent specific applications of graphene-based composites, from electrochemical capacitors and lithium-ion batteries to emerging electrochemical energy storage systems, such as metal-air and metal-sulfur batteries. The new features and challenges of graphene-based composites for electrochemical energy storage are also summarized and discussed. This review is specifically aimed at offering new perspectives on the combination of graphene with other electrochemical materials to optimize their performances, and will outline ways to further improve graphene-based composites towards the next generation of electrochemical energy storage devices.