Steve Nash shook off a poor first half to score a season-high 32 points and O'Neal scored 17 points on his 37th birthday for the Suns.
The Rockets led most of the way, but Nash made his fourth 3-pointer with 30 seconds left to tie it at 112.
With the shot clock running down for the Rockets, Yao set a high screen for the 6-foot Brooks, who beat O'Neal to the basket with an underhanded layup with 7.3 seconds left.
Nash missed a 3-pointer off the front of the rim on the Suns' final play. Artest rebounded and made two free throws with 0.3 seconds left.
The Suns have lost four straight road games and slipped three games behind Dallas in the race for the No. 8 playoff spot in the West. The Rockets moved ahead of New Orleans for fourth place in the conference.
Before Brooks and Nash dueled in the second half, the talk before the game was the matchup between Yao and O'Neal.
Yao blocked O'Neal's first shot 20 seconds into the game, but Luis Scola carried Houston early, grabbing five rebounds and scoring eight points in the first 8 minutes.
Robin Lopez replaced O'Neal with 4:36 left in the first quarter and Yao blocked Lopez's first shot, part of the Suns' 3-for-14 start.
The Rockets led 23-18 after the first quarter, and Nash and Leandro Barbosa made 3-pointers early in the second quarter to give the Suns their first lead, while O'Neal struggled. He missed 4 of his first 6 shots and lost the ball to 6-foot Kyle Lowry.
O'Neal sent Yao to the floor on an offensive rebound and dunked to cut Houston's lead to 37-34, but the Rockets answered with a 7-0 burst to stretch the lead to 10.
Nash had a worse first half than O'Neal, going 1-for-10 from the field, and Houston led 56-46 at the break.
