Moyes' Blue revolution took just 32 seconds to take effect when David Unsworth fired Everton into the lead at Goodison Park.
Duncan Ferguson scored their second on his return from injury and at that point Everton seemed set for a comfortable three points.
But the game then changed dramatically when Thomas Gravesen was sent off and Fulham pulled a goal back through Steed Malbranque.
However Everton hung on to claim three vital points, even though the second half was like a re-run of the Alamo.
Moyes had claimed at his unveiling on Thursday that he wanted to bring some stability to the club after the revolving door transfer policy of the last few years.
Those hopes were dashed before kick-off when Paul Gascoigne joined Burnley on loan to seek yet another fresh start.
David Ginola could soon be following him through the exit and the veteran Frenchman did not even make the bench, nor did Tobias Linderoth.
Ferguson returned from his double hamstring strain to captain the Blues, while Gravesen, Lee Carsley and Tony Hibbert also started against unchanged Fulham, who had never won a league match at Goodison.
A quick glance at the league table revealed why Everton had replaced Walter Smith with fellow Scot Moyes.
Only goal difference was keeping Everton out of the relegation zone before this game after a miserable run of one win from their last 13 Premiership matches.
Moyes received a tremendous reception from the Everton fans when he was presented to them just before kick-off.
And they were cheering again after just 32 seconds when Ferguson knocked
Alessandro Pistone's throw-in to Tomasz Radzinski, who laid the ball back to
Unsworth and he blasted a left-foot rocket past Edwin van der Sar.
It was only Everton's fifth goal in their last 13 Premiership matches. On 13 minutes it became 2-0 when Ferguson, who was being watched by new Scotland coach
Berti Vogts - who hopes to persuade him to play for his country again – scored his first Premiership goal since August 20.
Van der Sar's weak clearance came off Ferguson and the big striker was first to the rebound to sidefoot the ball home.
Fulham eventually regained their senses and Everton goalkeeper Steve Simonsen parried a shot from Malbranque.
Then, on 27 minutes, the over-officious Graham Barber, who has amassed more bookings this season than any other referee, showed Gravesen a second yellow card for a late tackle on Luis Boa Morte and dismissed the Dane. Gravesen had been booked earlier, also for a foul on Boa Morte.
Both teams were fined after a mass brawl when they last met in December and Barber booked Unsworth and Malbranque as tempers threatened to boil over again.
The sending off changed the game and Fulham sensed they might yet get something out of this match to end their run of four successive league defeats.
The lively Malbranque twice went close again before Ferguson headed a curling free-kick from the Frenchman off his own line.
Both sides made changes at half-time and Fulham threw on Barry Hayles and Abdeslam Ouaddou while Everton replaced Radzinski with Joe-Max Moore.
Fulham continued to do all the attacking and Everton all the defending. The visitors' pressure paid off on 52 minutes when Hayles got to the byline and pulled the ball back for Malbranque to stab the ball home from around six yards out.
Moyes, who after 13 minutes must have thought this Premiership lark is a doddle, looked increasingly anxious and he paced his technical area bellowing instructions.
Nerves were also beginning to fray on the pitch and Barber had a word with Malbranque and Alan Stubbs after the pair squared up to each other.
Fulham were now camped on the edge of the Everton box and it seemed only a matter of time before Jean Tigana's side equalised.
Moyes brought on Jesper Blomqvist for Unsworth in an attempt to stem the tide, but still Fulham, who replaced Legwinski with Bjarne Goldbaek, kept coming.
Louis Saha thought he had done it with five minutes remaining, only to see his effort come off the crossbar.
That proved to be Fulham's last chance and, when the final whistle went, Moyes turned to the Everton fans behind him with a clenched fist and a broad smile on his face.