Andy Webster headed home a first-half opener and Rudi Skacel doubled the visitors' advantage with 15 minutes remaining.
Their second successive league victory lifts Hearts to fourth place in the Scottish Premier League.
Dunfermline made a bright start and Danny Grainger had to be alert to deal with a dangerous Joe Cardle free-kick in the opening minutes.
The first opportunity for the visitors came after 11 minutes when David Templeton weaved into the Dunfermline box and got a strong shot away only for Paul Gallagher to deflect the ball round the post for a corner.
Hearts' Ian Black limped off after 21 minutes and was replaced by former Kilmarnock midfielder Mehdi Taouil.
Taouil's introduction seemed to breathe life into Hearts and two minutes after coming on the Moroccan produced an excellent delivery from the right which required Andy Dowie to head clear under pressure from Templeton.
A superb diving stop from Gallacher denied Rudi Skacel with five minutes remaining in the first half and the visitors grabbed the opener from the resulting corner.
Grainger's delivery was not dealt with by the home defence and Webster was able to head home from close range.
On 43 minutes Paul Burns hauled down Taouil as he steamed through on goal to earn the first yellow card of the game.
Dunfermline showed more attacking intent at the beginning of the second half but were unable to put any pressure on Hearts keeper Marian Kello.
The visitors still looked the more likely to extend their advantage and Gallagher was forced to make a vital interception from Grainger's cross.
Two minutes later Ryan Stevenson was felled by John Potter at the edge of the Dunfermline box. Jamie Hamill set up Grainger from the resulting free-kick but his fizzing effort was well off target.
Stevenson passed up a gilt-edged chance just before the hour-mark when he met Templeton's cross but could only head into the arms of Gallagher.
Dunfermline manager Jim McIntyre introduced Liam Buchanan in place of Joe Cardle after 61 minutes.
Potter forced Kello into his first save of the match after 69 minutes when his dangerous cross almost caught the Czech stopper out at his far post.
The home side suddenly seemed to be building momentum and full-back Paddy Boyle unleashed a sensational strike from 25 yards out which went inches over the bar.
Their hopes of a comeback were dashed with 15 minutes remaining however as Hearts grabbed the vital second goal.
Boyle's misplaced pass was intercepted by David Templeton who drove through on goal and unleashed a stinging effort which was well saved by Gallagher, unfortunately for the keeper though Skacel was on hand to drill the rebound home - much to the delight of the huge travelling support.
Immediately after the goal Dunfermline made a double substitution with Pat Clarke and Paul Willis coming on in place of Andy Kirk and Ryan Thomson.
Hearts boss Paulo Sergio made some changes of his own in the closing stages as he replaced Skacel and Stevenson with David Obua and John Sutton.
In injury-time Boyle missed a good opportunity to grab a consolation goal for Dunfermline when he found space at the back post but his tame effort was easily gathered by Kello.