Realization of the quantum-spin-Hall effect in graphene devices has remained an outstanding challenge dating back to the inception of the field of topological insulators. Graphenes exceptionally weak spin-orbit coupling -stemming from carbons low mass- poses the primary obstacle. We experimentally and theoretically study artificially enhanced spin-orbit coupling in graphene via random decoration with dilute Bi2Te3 nanoparticles. Remarkably, multi-terminal resistance measurements suggest the presence of helical edge states characteristic of a quantum-spin-Hall phase; the magnetic-field and temperature dependence of the resistance peaks, X-ray photoelectron spectra, scanning tunneling spectroscopy, and first-principles calculations further support this scenario. These observations highlight a pathway to spintronics and quantum-information applications in graphene-based quantum-spin-Hall platforms.