Murray, who was knocked out in the fourth round in Melbourne, had to work for 45 minutes to win the opening set.
The top seed, now fully fit after a bout of shingles, beat Malek Jaziri 6-4, 6-1, avoiding the fate of second seed and title holder Stan Wawrinka, dumped out as his form collapsed following an early 4-1 lead.
"I was a little bit uneasy, I've never hit with him or played against him before," Murray said. "It took a little bit of time to get used to his game."
"But I played better as the match went on. I don't feel sore anywhere, really. I felt like I moved good and the body felt good."
Murray, who was knocked out in the fourth round in Melbourne, had to work for 45 minutes to win the opening set but the Scot ran away with the second against the outclassed Jaziri.
Murray will now face Spain's Guillermo Garcia-Lopez on Wednesday.
In contrast, the Swiss three-time Grand Slam winner Wawrinka was beaten 7-6 (7/4), 6-3 in the first round by outsider Damir Dzumhur.
Wawrinka was playing for the first time since suffering a right knee injury in Melbourne, where he reached his eighth major semi-final before falling to compatriot Roger Federer.
Following defeat by the 77th-ranked journeyman from Bosnia-Herzegovina, he admitted that his fitness was lacking after only a week of practice.
"I started well but it was tough because I was missing a little bit of something. In practice it was starting to be OK the last few days, but today I was missing something."
Dzumhur will now face Marcel Granollers of Spain.
"This is a big win for me, coming on hard court against a player who likes this surface and who won the tournament last year," the surprise winner said.
After taking an early lead, Wawrinka found his game slipping. By the time he got the first-set tiebreak, he was playing catch-up.
The Swiss was broken twice for 5-1 in the second set before a brief rally in which he broke back once.
Despite his exit Wawrinka said that his knee was giving him no pain, a positive sign heading into back-to-back Masters 1000 events starting next week in Indian Wells and Miami.
"I need to focus on myself. I need to practise more, to get in a better level to expect to do some good results," Wawrinka said.
"I'm quite unhappy to lose the first round. It's tough because I played well last year here. I was happy to be back. I was happy to be back on the ATP Tour after a month."
Fifth seed Tomas Berdych needed just half an hour to win after fellow Czech Lukas Rosol quit with a knee injury trailing 6-3, 2-1.