It was 342 days since former world number one Murray last took to court in a competitive match, a Wimbledon quarter-final loss to Sam Querrey last July before he needed hip surgery in January.
Kyrgios and Murray are good friends, and the Scotsman was not expecting to win, but came up against an opponent who at times did not look interested in playing as he shook his head throughout the match.
Murray won the first set before Australian Kyrgios produced some superb shot-making to progress to the last 16. It his first win over Murray and a first win at Queen's.
Cilic stuns Djokovic to claim Queen’s Club title
The 31-year-old Murray looked on course for a dream return from right hip surgery as he took the first set against the erratic Australian but eventually succumbed 2-6 7-6(4) 7-5.
While the result, his first defeat in six matches against Kyrgios, was not what most of those on a sun-kissed centre court had wanted to see, Murray's general play and mobility were a heartening sight as Wimbledon approaches.
Despite looking fatigued near the end, the old fighting spirit was alive and well as he saved two match points at 4-5 in the decider. Kyrgios then saved a break point at 5-5 and an engrossing duel ended when Murray double-faulted.
Kyrgios had looked distracted in the opening set, surrendering three service games with wild double-faults and playing several outrageous party shots, but he buckled down and played some outstanding tennis.
"Obviously we are good mates and it was great to see him back and healthy," Kyrgios, who lost to Roger Federer in the semi-finals on grass in Stuttgart last week, said.
"I asked him at the end if he felt healthy and he said yeah, which is the main thing.
"It was nice to finally get a win over him but I can't really count it. He came out really good and I kind of expected that. Personally I feel good. I was out for two-and-a-half months so I'm feeling good."
The Australian will now face British number one Kyle Edmund in the next round, after the 23-year-old set up the last-16 clash with victory over American Ryan Harrison.
Showing the sort of form that has taken him into the top 20 in the world, Edmund progressed in straight sets 7-6 6-4 and said he was delighted to be back playing in front of a home crowd.
"It's always great when you play in front of your home crowd," he said. "First of all, thanks to everyone for supporting me, it's great to be back in the UK playing tennis again.
"I didn't get off to the best of starts and maybe there were some pre-match nerves, which is completely normal for the first match on grass in your home country.
"I was very pleased to break back the next game and after that game I found I settled into the match and really got my game on court.
"Although the second set was kind of close I was always knocking on the door of breaking him and I broke him to win the match."
Edmund also welcomed the return of Murray following his long absence from the game. "It was just great to see Andy back on court to be honest," he added.
"Knowing how much he's done in the game and how much he's helped me personally, it's been tough for him to not play, I'm excited to see him back on court."
Relentless Cilic edges Kyrgios to set up Djokovic final
Kyrgios overcomes Edmund to reach last eight