Both \ and * are special in a regular expression, which means that to match them literally you have to use a backslash to escape them. What you've done is just escape the special meaning of the *; you need s#\\\*#STAR#g to match the literal characters \* (the first \\ matches a single backslash, then the \* matches a single *). Read perlretut and perlre for more details.