An interconnect structure may include a graphene-metal barrier on a substrate and a conductive layer on the graphene-metal barrier. The graphene-metal barrier may include a plurality of graphene layers and metal particles on grain boundaries of each graphene layer between the plurality of graphene layers. The metal particles may be formed at a ratio of 1 atom % to 10 atom % with respect to carbon of the plurality of graphene layers.