Robinho made amends to put the Rossoneri ahead following a first-half penalty miss before Nigel de Jong placed an exquisite curling shot beyond Vicente Guaita to double Milan's lead.
Valencia pulled a goal back early in the second half as Daniel Parejo netted from close range, however, despite their persistence, los Che could not find that elusive equalizer.
And perhaps it would have had Valencia coach Miroslav Dukic included captain Roberto Soldado in his lineup but the striker's absence was somewhat explained by the interest shown in him from Premier League clubs.
Instead, Dukic opted for 19-year-old Francisco Alcacer up front, while Milan included new signing Andrea Poli and star duo Kevin-Prince Boateng and Robinho in their starting lineup.
And it would be the Brazilian who would have the chance from 12 yards to put the Serie A club ahead against the run of play as Valencia goalkeeper Guaita foolishly decided to bring down Poli near the byline in the 21st minute.
Robinho – who missed a penalty in a midweek friendly against Juventus – again failed to convert from the spot, as Guaita pulled off a one-handed save, with Valencia's defenders reacting quickly to clear the danger emanating from the rebound.
But the 29-year-old, who had been linked with Santos this summer, made amends less than a minute later drilling a low shot from the edge of the penalty area across Guaita and into the left corner after a fine assist by Poli.
It was a terrific finish but drama was to follow for Robinho as he pulled up with a suspected groin problem shortly after, and a melee ensued as Valencia refused to kick the ball out and nearly scored through Alcacer.
Antonio Nocerino and Boateng were shown yellow cards for their involvement in the fracas.
The frenetic nature of the match continued as an Adil Rami header was disallowed for offside, while Feghouli wasted a terrific chance moments later for the hosts.
Boateng also had a goal disallowed following a foul at a Milan corner before De Jong scored a stunning second for the Serie A side.
The Ghanaian fed the ball to the former Manchester City midfielder and from 25 yards he curled a superb effort into the top-right corner, giving Guaita no chance.
De Jong hit a free kick just wide on the verge of halftime, with the break allowing both sides and the fans to catch their breath.
Diego Alves replaced Guaita in goal for Valencia, while Gabriel came on in place of Christian Abbiati and Sulley Muntari was introduced for Milan.
Rami hit a left-foot effort that went just wide early in the second half, while Kevin Constant did the same at the other end.
Valencia did get their goal though, as an excellent Jonas chip found Alcacer in the penalty area, and the youngster had the presence of mind to square for Parejo, who simply side-footed past Gabriel.
It was a deserved goal and Alcacer went close himself just after, while Banega had a good free-kick fizz just wide.
Valencia continued to press, as Faghouli turned an effort just wide, while Alcacer and Michel both had attempts on goal.
The hosts were desperately unlucky when Federico Cartabia thrashed a 30-yard effort against the underside of the bar, while he fired over shortly after.
Oriol Romeu then clipped the crossbar with a cross and Cristian Zaccardo cleared Alcacer's effort off the line, but it was not to be as Milan grimly held on for victory.
Milan will now play the winners of Chelsea or Inter in New York on August 4.