Richarlison scored his first goals of the season while Alex Iwobi and Bernard also got off the mark as Everton saw off the challenge of Joey Barton's Fleetwood.
Moise Kean came off the bench to round things off with a simple finish for the fifth goal thanks to brilliant work down the left by Niels Nkounkou as the Blues won 5-2 in successive matches to book a date with West Ham at Goodison Park next week.
Carlo Ancelotti named a starting XI with a healthy mix of established starters and players looking for another opportunity to impress as Dominic Calvert-Lewin and Richarlison started up front ahead of a midfield that also featured the returning Fabian Delph.
Everton dominated the first half and could have been a goal up with just six minutes on the clock but Nkounkou's dangerous ball from the left just eluded Calvert-Lewin flying in towards goal.
Nkounkou's trickery a few minutes later ended with another cross that Calvert-Lewin met but his header was blocked before Iwobi's deflected shot rattled the top of the crossbar in the 21st minute.
Everton made the breakthrough a couple of minutes later, though, thanks to a goal made in Brazil. Bernard collected the ball in space 10 yards outside the Fleetwood box and he flighted a beautiful ball into the box for Richarlison to stoop and guide past Alex Cairns.
Iwobi and Bernard curled almost identical shots inches past the post in the 30th and 32nd minutes but it was merely a delay to the inevitable which swiftly followed.
Richarlison drove into the box and laid the ball off to Iwobi who back-heeled it superbly into the Brazilian's path where a first-time prod doubled the visitors' lead.
2-0 almost became 3-0 in first-half stoppage time but when Michael Keane picked Calvert-Lewin out with a terrific forward ball, Cairns pulled off an impressive reaction save to palm his effort wide.
That would be Calvert-Lewin's last contribution as he was withdrawn at the interval in favour of Anthony Gordon whose added positivity and direct running would prove vital in the second period.
Jordan Pickford may not have touched the ball in the first period but his clownery was instrumental in giving Fleetwood the belief they needed to make a game of it in the first 15 minutes after half-time.
The England keeper tried to dribble Keane's pass to get away from two opposition players on the edge of his six-yard box and when his attempted clearance ricocheted back towards the penalty spot, Fleetwood's substitute Matt Duffy was on hand to rifle the loose ball home.
Iwobi restored Everton's two-goal cushion almost immediately when Gordon powered in from the left and cut the ball back, Richarlison air-kicked it from close range but the Nigerian was well-placed to comfortably convert behind him to make it 3-1.
The lead was halved again, however, just moments after Iwobi had swept another shot just wide. Glenn Whelan sent a deep ball to the back post that Pickford elected not to try and claim, Ched Evans headed it back across goal where Callum Camps's overhead kick was only partially blocked by the keeper. and it crept in.
Josh Morris forced Pickford to push a shot away from distance as Fleetwood threatened to complete their comeback but after Tom Davies came on for Delph and the Toffees settled themselves down again, they eventually regained control.
Bernard forced another stop from Cairns with a curling shot from the left but it was Gordon, driving down the right flank this time, who laid on the fourth goal. His centre kicked up invitingly off a defender's foot for Bernard who crashed a first-time shot down the centre of the goal from about 10 yards out to make it 4-2.
That appeared to be that even though Kean replaced Richarlison and Gordon volley narrowly wide in the closing stages but there was time for one more attack, instigated by stand-in centre-half, Lucas Digne, in the final minute of injury time.
The Frenchman sent his compatriot Nkounkou down the line with a perfectly-weighted ball over the top that the latter collected and ran with until he got into the area where he back-heeled it cheekily into the path of Kean who was arriving to side-foot home with ease.
It capped another eye-opening display by the young French fullback who was many people's man of the match last week against Salford and who likely took the accolade in this tie as well.
Richarlison may have scored twice in what was a typically energetic performance, Digne was commendable playing out of his natural position at centre-half and Gordon was laudably forward-looking when he came on at the break but it was Nkounkou, a player who never made a senior appearance for Marseille, who was the stand-out on the night.
While Ancelotti will continue to have concerns over his goalkeeper and the need for cover at centre-back remains acute, he will have been buoyed by the way Bernard and Iwobi in particular seized their chances in midfield.
Everton travel to Crystal Palace on Saturday having won their first four games in all competitions for the first time since 1978 and then welcome the Hammers to Merseyside in the Carabao Cup next Wednesday night (Kick-off 7:45) knowing that victory there would put them into the quarter-finals of a cup competition before a month of the new season will have elapsed.
Everton saw another slew of goals in their latest Carabao Cup venture to Fleetwood Town on a wet Wednesday evening, two brilliant ones from Richarlison in a scintillating first half.
Keane and Digne were partnered at the back again, Richarlison and Calvert-Lewin leading the line and there was a Fabian Delph sighting in midfield. Gordon and Kean were only on the bench for this one but it was another great chance for Nkounkou to shine.
The home side kicked off but the all-Blues took early control of the ball, Nkounkou again looking good down the left. After total midfield domination, a great cross was finally delivered but cleared. A blatant handball by a Fleetwood defender was completely ignored by the referee./p>
Another brilliant cross fro Nkounkou was inches away from being converted by Calvert-Lewin. At the other end, Delph had to be clinical with a fine tackle in is box, giving away the first corner.
Iwobi should have put in Kenny for across but his passing was poor. On the other side, Nkonkou put one right n a plate, but Calvert-Lewin again seemed incapable of directing it goalward. Kenny dug out a cross but straight to the keeper.
Richarlison got past Burns but then overhit his cross. Bernard gave the ball away as Blues' plays started to look a little too sloppy, intricate passing just not coming off.
Calvert-Lewin was fouled in a promising position but Digne lamely whacked the ball into the wall. Nkounkou crossed low but this time no Blue shirt receiving. For all the Blues dominance, nothing really until Iwob's shot was deflected up onto the bar.
A long clearance from Pickford was aimed at Calvert-Lewin but headed clear to Iwobi who fed Bernard. A lovely chip from Bernard was buried by Richarlison, a firm header to finally break the deadlock on the quarter-point of the game.
Digne launched a corner very deep that a back-peddling Calvert-Lewin could only head to a defender. Everton continued to circulate the ball around midfield and the margins of the Fleetwood area without really threatening, another super Nkounkou cross in avoiding everyone and Iwobi dragging a shot wide.
Bernard created great space for himself to shoot... wide. But then some absolutely fantastic individual brilliance from Richarlison on the left brought a wonderful toe-poke strike from him, thanks to a brilliant backheeled one-two off Iwobi, what an excellent goal!
Sigurdsson tried to get himself on the scorecard but his shot was blocked too easily at source. His corner, and then cross were no better. Nkounkou overlaped Richarlison and flashed another brilliant cross... no dice. Blue shirts simply not interested! Kenny drove in from the right and seemed to have a good chance but just wellied it sky high. Awful shot.
Iwobi tried again but his attempt was blocked. Kenny was trying but struggling to make the link-up with Iwobi work on the right. A lovely delivery right on the money to Calvert-Lewin but no first touch from him as he had to take it on his chest; however, he surely should have been far more clinical after controlling the ball well. But no, his shot was never going to beat the keeper. Everton's passing stats must be amazing for a very one-sided first half.
A ridiculous moment from Pickford at the start of the second half threatened to spoil the night as he gifted a goal to Duffy. But Everton went up the other end and Gordon, on at the break for the very poor Calvert-Lewin, fed Iwobi with a great cross that Richarlison, let's say he dummied it, before the ex-Arsenal man buried his shot.
Great set-up play by Richarlison was inch-perfect for Iwobi who drilled his shot agonizingly wide. At the other end, a very nicely worked and finished goal with an acrobatic shot by Camps that Pickford parried but could not keep out.
Pickford then had to keep out a lively snapshot from Morris as Fleetwood saw some real chinks open up invitingly in Everton's defence. Ancelotti made his second change, Davies on for Delph.
Richarlison tried to create more magic with a sharp turn but he was being closely attended. After a stale spell, Gordon tried to tee up Bernard but the Brazilan saw his effort go behind for a corner which was defended clear far too easily.
Everton were labouring to get close enough for clear chances, Nkounkou getting blocked for a corner taken by Sigurdsson that came to nothing. But the ball bounced up nicely for Bernard to volley in the fourth goal on another feed, this time from the right, from Gordon that again evaded Richarlison on it's way to the goalscorer.
Gordon scampered forward on the left this time but, lacking support, he could only strike at the goalkeeper. Jonjoe Kenny then set up Gordon with a beautiful chance to volley in the fifth but he drove it disappointingly wide of the target.
At the death, a fine goal for Kean, created by more excellent work by Nkounkou to round things off in fine style with another 5-2 win for the Blues!
Scorers: Richarlison (22', 34'), Iwobi (49'), Bernard (73'minutes), Kean (90+4')
Fleetwood Town: Cairns, Burns, Stubbs (46' Duffy), Hill, Andrew, Coutts (75' Matete), Whelan, Josh Morris, Camps, Boyes, Evans (75' Saunders).Subs not Used:Leutwiler, Garner, Holgate, Shayden Morris.
Everton: Pickford, Kenny, Keane, Digne, Nkounkou, Delph (62' Davies), Sigurdsson, Iwobi, Bernard, Richarlison (76' Kean), Calvert-Lewin (46' Gordon).
Subs not Used: Lössl, Coleman, Doucouré, Walcott.
Everton take their next step in what is a compressed start to the 2020-21 edition of the Carabao Cup when they travel to Fleetwood Town on Wednesday evening.
Having seen off League Two Salford City in the second round a week ago, the Blues now face League One opposition in the form of Joey Barton's side but, with another important Premier League game looming on Saturday, Carlo Ancelotti is expected to make a significant number of changes to his starting XI.
Against Salford, Michael Keane was the only player to start that match and the season-opener at Tottenham and it's likely to be a similar situation in this tie, although the injury crisis at centre-back means that both Keane and Yerry Mina are likely to be in the line-up.
However, the Colombian's own injury niggles since he arrived at Goodison two years ago might see Ancelotti err on the side of caution and deploy a makeshift centre-half instead.
Lucas Digne came on after 24 minutes against Salford when Jarrad Branthwaite had to go off with torn ankle ligaments to fill in at centre-half but both Jonjoe Kenny and Seamus Coleman can operate there as well, as can Fabian Delph who might be in the running to play if he is finally passed fit.
The only other fit option with any first-team experience was Lewis Gibson but, as expected, he has sealed a season-long loan move to Reading and won't be available to play against Fleetwood, the team for whom he had a spell on loan last season.
In goal, Joao Virginia is expected to be able to celebrate his new 4-year contract by making his second start and Kenny will probably get the nod at right-back again. Meanwhile, Anthony Gordon, Niels Nkounkou and Moise Keane will be hoping to get another opportunity to shine.
The remaining spots will be contested by the likes of Alex Iwobi (who could come in on one flank given how poor Theo Walcott was against Salford), Bernard, Delph, Tom Davies (if he is fit) and Gylfi Sigurdsson.
None of the new signings are expected to be involved from the start and, if Ancelotti opts for a similar approach to the last round, James Rodriguez will be rested completely.
Fleetwood, now managed by boyhood Evertonian, Joey Barton, were promoted to the Football League for the first time eight years ago and took the step up to English football's third tier in only their second season.
Barton took over as the long-term successor to Uwe Rösler in 2018 following John Sheridan's interim tenure and steered the Fishermen to an 11th place finish in 2018-19 and then into the playoffs last season where they lost to Wycombe Wanderers.
This season, they sit 11th after two games having beaten Burton Albion but lost to Peterborough United. As such, they should pose more of a challenge than Salford did, particularly as they have the benefit of playing in the more familiar environs of their Highbury Stadium.
Ancelotti will hope that, even with another much-changed side, his Blues can get the job done and book their place in the 4th Round where they would meet West Ham United at Goodison Park.
Kick-off: 7:45pm, Wednesday, 23 September 2020
Live coverage is on Sky Sports Football and Sky Sports Main Event, starting at 7:30 pm.