Oncolytic vesicular stomatitis virus (VSV) is being developed as a novel therapeutic agent for cancer treatment, although it is toxic in animals when administered systemically at high doses. Its safety can be substantively improved by an MΔ51 deletion in the viral genome, and yet VSV(MΔ51) induces a much greater, robust cellular inflammatory response in the host than wild-type VSV, which severely attenuates its oncolytic potency. We have reported that the oncolytic potency of wild-type VSV can be enhanced by vector-mediated expression of a heterologous viral gene that suppresses cellular inflammatory responses in the lesions. To develop an effective and safe VSV vector for cancer treatment, we tested the hypothesis that the oncolytic potency of VSV(MΔ51) can be substantively elevated by vector-mediated expression of M3, a broad-spectrum and high-affinity chemokine-binding protein from murine gammaherpesvirus-68. The recombinant vector rVSV(MΔ51)-M3 was used to treat rats bearing multifocal lesions (1-10 mm in diameter) of hepatocellular carcinoma (HCC) in their liver by hepatic artery infusion. Treatment led to a significant reduction of neutrophil and natural killer cell accumulation in the lesions, a 2-log elevation of intratumoral viral titer, substantively enhanced tumor necrosis, and prolonged animal survival with a 50% cure rate. Importantly, there were no apparent systemic and organ toxicities in the treated animals. These results indicate that the robust cellular inflammatory responses induced by VSV(MΔ51) in HCC lesions can be overcome by vector-mediated intratumoral M3 expression, and that rVSV(MΔ51)-M3 can be developed as an effective and safe oncolytic agent to treat advanced HCC patients in the future.