Current-perpendicular-to-plane (CPP) magnetoresistance (MR) effects are often exploited in various state-of-the-art magnetic field sensing and data storage technologies. Most of the CPP-MR devices are artificial layered structures of ferromagnets and non-magnets, and in these devices, MR manifests, due to spin-dependent carrier transmission through the constituent layers. In this work, we explore another class of artificial layered structure in which multilayer graphene (MLG) is grown on a metallic substrate by chemical vapor deposition (CVD). We show that depending on the nature of the graphene-metal interaction, these devices can also exhibit large CPP-MR. Magnetoresistance ratios (>100%) are at least two orders of magnitude higher than “transferred” graphene and graphitic samples reported in the literature, for a comparable temperature and magnetic field range. This effect is unrelated to spin injection and transport and is not adequately described by any of the MR mechanisms known to date. The simple fabrication process, large magnitude of the MR and its persistence at room temperature make this system an attractive candidate for magnetic field sensing and data storage applications and, also, underscore the need for further fundamental investigations on graphene-metal interactions.