The inherent properties of 2D materials—light mass, high out-of-plane flexibility, and large surface area—promise great potential for precise and accurate nanomechanical mass sensing, but their application is often hampered by surface contamination. Here we demonstrate a tri-layer graphene nanomechanical resonant mass sensor with sub-attogram resolution at room temperature, fabricated by a bottom-up process. We found that Joule-heating is effective in cleaning the graphene membrane surface, which results in a large improvement in the stability of the resonance frequency. We characterized the sensor by depositing Cr metal using a stencil mask and found a mass-resolution that is sufficient to weigh very small particles, like large proteins and protein complexes, with potential applications in the fields of nanobiology and medicine.