And although Connacht responded with a try from Danie Poolman, Dan Parks' missed drop-goal with 90 seconds left proved vital as Edinburgh held on.
Edinburgh head coach Michael Bradley welcomed back his Scotland stars as he named a strong line-up to build on last week's RaboDirect PRO12 victory over champions Ospreys.
And returning winger Tim Visser pounced on a mix-up in the Connacht midfield to race through in the sixth minute and touch down. Greig Laidlaw with the conversion.
Connacht responded four minutes later though and capitalised on a lineout as a powerful maul allowed flanker Willie Faloon to cross. Dan Parks added the extras to level things up at 7-7.
The visitors then edged in front once more as captain Laidlaw kicked a straight-forward penalty.
But not to be outdone former Scottish international Parks added a penalty of his own to level it up once more after Perry Parker was penalised for tackling with the arms. 10-10.
The two bottom-half sides then sought to feel each other out as the next 14 minutes failed to yield a single point.
But Laidlaw showed his international class once more with a sublime chip which found the onrushing Matt Scott who stepped the last man and went over for a 17-10 lead.
But Parks' steady boot reeled back some of the deficit just before half-time as Edinburgh were penalised at the scrum.
It took a while for either side to get going again after the break but Parks was yet again gifted the opportunity to close the gap which he duly took as it became a one-point game on the hour.
Edinburgh however responded and from their own 10m line sculpted an expert break involving Visser, Chris Leck and Nick De Luca, but a finger tip knock-on at the line meant the chance went begging.
But just five minutes the try finally came as the ball was recycled quickly after a 40-metre break from Denton and found McInally who touched down under the posts.
Laidlaw made no mistake with the conversion as Edinburgh gave themselves some breathing space but a pulsating finish followed.
Connacht came charging back and, after forcing their way forward on the right spun the ball left for Poolman who went over with Parks adding the extras with nine minutes remaining.
And the Irish side looked destined to score again five minutes later with a man in space but at the key moment, agonisingly knocked on with one point still between them.
The scene was set soon after for Parks who, dropping into the pocket, attempted the drop-goal only to see his effort slide wide with 90 seconds left.
And with the 80 minutes complete a turnover by Edinburgh on the halfway line ended proceedings as the Scottish side revelled in an impressive away victory.
|Connacht Rugby Score Card|
|Edinburgh Rugby Score Card|