Andrea Mandorlini's side, the surprise package of the season so far following their return to the top flight, headed into the contest on the back of three consecutive victories, with Inter winless from as many games.
But horrible defending from set-pieces undermined their cause as a Vangelis Moras own goal and Rodrigo Palacio set Inter on the way.
Former Italy striker Luca Toni laid on goals for Raphael Martinho and Romulo but each time it only reduced the deficit to two after Esteban Cambiasso and Rolando gave Walter Mazzarri's men much-needed breathing space.
Juan Pablo Carizzo came in for the suspended Samir Handanovic in goal for Inter, who also welcomed Ricky Alvarez into the fold.
Inter started on the front foot and took the lead in the ninth minute as Verona defender Moras diverted Jonathan's wildly off-target volley into his own net.
Verona's defending from corners was haphazard throughout the first half and it cost them again three minutes later. A loose ball fell to Fredy Guarin and his strike was blocked on the line by Fabrizio Cacciatore, only for the rebound to strike the fortuitously placed Palacio and go in.
Midway through the half Toni passed up a chance to reduce the deficit when he headed over after Cacciatore beat Yuto Nagatomo to whip in a superb cross from the right.
Inter thought they had a third in the 32th minute but Guarin waited too long in releasing his pass after driving at the Verona defence and Palacio was offside when he converted.
It appeared a costly error less than a minute later when Verona charged up the other end to reduce their arrears - Toni holding off a pair of challenges and playing in Martinho to finish emphatically.
But the two-goal advantage was restored before the break when the impressive Nagatomo cut in from the left to strike the post, Palacio helped the loose ball back towards goal and Cambiasso obliged with the net gaping.
Palacio stabbed home a long ball forward, only to be denied by the offside flag once more, and another of the game's familiar sights reared its head in the 56th minute.
A low corner to the near-post by Cambiasso was helped on by Palacio and Rolando was on hand to bundle home.
Mazzarri removed Palacio and Cambiasso as Inter looked to take the sting out of the game but Toni thought little of their plan, again making his physicality count before squaring for Romulo to drill a fine finish into the bottom corner.
But the hosts held on without any other major alarms to leapfrog their opponents and go fourth in the table, before the evening ended in bizarre circumstances when Moras and Inter substitute Ishak Belfodil were sent off after the final whistle following an altercation.