According to legend , it was originally named Mons Martyrum ' where , after being decapitated , the town 's first bishop , Saint Denis , picked up his head and walked away .
Saint Denis had been executed for proselytizing the Christian faith .