At some point after CT, Masa and Mune went to sleep. We don't know when, or how. In 1005, the Masamune was stolen, and used to massacre a ton of people. It was mostly this event that turned the sword red and evil looking. We don't know if it actually became evil at that point, or was already evil since Masa and Mune fell asleep. After that, there it possible made its way to Denadaro Mts for Radius to kill Gairi, or it made its way to El Nido for Radius to kill Gairi. I personally believe its the former. But regardless, after Gairi's death, it was in El Nido. How it moves from Guardia to (possibly) Denadaro, to El Nido is not known.