The result has seen Man United move three points clear of Manchester City at the top of the Premier League table, with the second-placed Citizens away to the champions Chelsea in the late kickoff.
Palace, meanwhile, remain rock bottom of the table on zero points, and the Eagles are now without a single goal in their opening seven Premier League matches of the 2017-18 campaign.
Antonio Valencia, Phil Jones, Fellaini, Mata and Marcus Rashford all returned to the Man United XI following the clash with CSKA Moscow on Wednesday night, which saw the likes of Eric Bailly, Ander Herrera and Anthony Martial drop to the bench.
As for Palace, Christian Benteke and Ruben Loftus-Cheek missed out through injury, while Timothy Fosu-Mensah was ineligible to face his parent club, which saw Joel Ward return to the team. Bakary Sako was the player picked to lead the line in Benteke's absence as the Eagles went in search of their first league goal of the season.
It took the home side just three minutes to make the breakthrough at Old Trafford, with Mata finding the bottom corner with a super finish after Rashford had driven down the left before picking out the Spaniard.
Palace had a decent chance to level the scores in the eighth minute when Mamadou Sakho met a free kick from Yohan Cabaye, but the former Liverpool centre-back saw his header miss David de Gea's crossbar.
Nemanja Matic was next to come close for Man United after finding space just outside the Palace box, but the Serbian missed the target as the score remained 1-0 to the hosts with 10 minutes on the clock.
Palace were struggling to create chances, but the Eagles were full of running in the final third, with Cabaye quick to join Sako in Man United's half of the field, and the visitors threatened from a couple of corners before the 30-minute mark.
Sako brought a decent save from De Gea in the 33rd minute as Palace continued to offer a threat, while Man United were struggling to get going as a series of misplaced passes led to groans from the home supporters.
Mourinho's side doubled their lead in the 35th minute, however, when fit-again Fellaini converted a brilliant Ashley Young cross at the far post as Palace were hit with a killer blow 10 minutes before the break.
Smalling almost made it three in the latter stages of the first period after meeting a deep corner from Mata, but the centre-back headed just wide, before Rashford hit the post from close range moments later as the referee's whistle was blown at 2-0.
Man United had a half-chance to score their third early in the second period when Rashford delivered a dangerous cross towards Lukaku, but Damien Delaney just about did enough to clear behind.
The home side would not take no for an answer at the start of the second half, however, and scored their third in the 49th minute when Fellaini headed a wonderful Rashford free kick into the back of the net from close range.
Young was next to come close for the Red Devils just before the hour, but the left-back's powerful attempt was kept out by Wayne Hennessey during a difficult period for the visitors.
Sako had a half-chance for Palace 20 minutes from time after meeting a cross from Townsend, although the stand-in forward's effort was always too high as Man United kept their clean sheet intact approaching the final stages.
Lukaku had a golden opportunity to put his name on the scoresheet in the 71st minute after breaking into the Palace box, but the centre-forward just passed the ball the wrong side of the post.
Palace continued to press forward in the latter stages, but it was Man United that had the better chances - Martial bringing a smart save from Hennessey, before Lukaku finally got his name on the scoresheet in the 86th minute after converting a low cross from Martial at the far post.
Next up for Man United is the small matter of a trip to Liverpool after the international break, while Palace's search for their first league point of the season will continue away to the champions Chelsea next time out.