"Malisse was hitting huge forehands and making it very difficult but I started playing higher towards the end of the first set which made it more difficult for him."
Murray has met third-round opponent Monfils three times before, winning twice.
"It will be a fun match against Monfils," said Murray, who won their last encounter on hard courts in Madrid in 2008.
"He is so fast, can jump incredibly high and reaches most balls, it's going to be difficult.
"I'm going to have to try and use some slice and angles to get him moving."
Malisse began confidently, his forehand in particular a potent threat as he broke Murray early on in the first set.
The Belgian, who beat world number 19 John Isner and Wimbledon finalist Tomas Berdych on the way to the semi-finals of the Legg Mason Classic in Washington DC last week, looked at ease as Murray struggled with a series of unforced errors.
But the turning point came in the 10th game when Murray's superior fitness allowed him to chase down a lob for a winner on the way to squaring the match at 5-5.
And the British number one broke again in Malisse's next service game to seal the first set before stepping up the quality in the second set.
After the match, Murray said he was enjoying working without a coach and reiterated that he was no hurry to appoint a new one ahead of the US Open.
Murray parted company with Miles Maclagan on 27 July after a two-and-a-half-year stint of working with his fellow Scot.
"When you're on your own, you have to play the way you like and come up with your own tactics, work things out on court a little better, and it's actually a nice feeling," he told BBC Sport.
"I guess I'll see how the next couple of weeks go and how I feel on the court.
"But I don't want to rush into making a decision just for the US Open and you end up with someone that isn't going to work and you aren't getting on with.
"I've got a break after the US Open when I'll probably sit down and have a long think about what I want to do and who I want to work with.
"That's probably the best time to do it because I don't want to make a bad decision before a Grand Slam."
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.