Moyes' side have crashed out of the Champions League, Uefa Cup and League Cup already this season and were close to being knocked out of the FA Cup by the Championship strugglers.
The impressive Marvin Williams opened the scoring for the home side when Ben May flicked a perfect ball over the top for the youngster to chase six minutes before half-time.
Williams, who signed a new two-year deal prior to the game, raced through to slot the ball past Richard Wright for only his second senior goal for the club.
Millwall set the alarm bells ringing in the Everton defence early on when the livewire Barry Cogan ran at the backline only to be bundled to the floor after just 13 minutes. Referee Rob Styles waved away the appeals from the Millwall players.
Tim Cahill was hoping to make a victorious return to the club he went all the way to the final with only two years ago and alongside Marcus Bent the Australian seemed Everton's best chance of scoring.
Indeed it was Bent who came closest first when Tony Hibbert picked him out in the penalty area with a perfect cross but the striker's header was poor.
Hibbert turned from provider to saviour just minutes later when he was called on to clear the ball off his own line. Cogan swung a dangerous corner into the box and May out-jumped the Everton defence and steered the ball towards the far corner, but Hibbert was on hand to clear the danger with Wright well beaten.
Everton's first real chance came on 33 minutes when an error by Paul Robinson saw the ball squirt to James McFadden on the penalty spot, but the young Scot was denied by a magnificent point-blank save by Andy Marshall who raced off his line to deny the winger.
Cahill was first to the rebound but the Australian international blasted the ball over the bar under pressure from Robinson who recovered well.
Moyes had seen enough on the hour and changed his side round as they went in search of the equaliser by bringing on James Beattie and Duncan Ferguson.
But it wasn't until the introduction of Osman than Everton looked a real threat in this game and his close-range header with just over 10 minutes to go earned his side a replay
After the goal it was a real backs-to-the-wall performance from Millwall as Everton threw everything at them but the Lions held on for a replay at Goodison Park.
Millwall – Barry Cogan. The 21-year-old former trainee belied his inexperience to produce a fine display and was a constant thorn in the over-worked Everton defence.
Everton – Tim Cahill. Returned to his former club and showed just how much he has progressed with an influential midfield display.