Fuller's first-half header ended Blackpool's remarkable 101-day wait for a win as Millwall boss Ian Holloway endured another unhappy Bloomfield Road return.
Striker Fuller's 14th-minute goal gave the hosts a 1-0 triumph and lifted the gloom which has engulfed the Seasiders since their last victory on November 30.
It also ensured caretaker boss Barry Ferguson won for the first time ever as a manager, against the man who brought him to Blackpool as a player in the summer of 2011.
The hosts certainly rode their luck with Matt Gilks saving a Steve Morison penalty almost immediately after the Seasiders had scored and the Lions twice hitting the woodwork in the first period.
But, after tasting defeat with Crystal Palace on his first return to the north-west coast last April, Holloway, who took Blackpool to the top flight, would leave defeated again as his men failed to muster enough in the second period.
Having not kept a clean sheet in eight home games, conceding goals had clearly been the crux of the Seasiders' problems during their slump and, after just three minutes here, another piece of sloppy defending should have seen Gilks' goal breached again.
Skipper Gary MacKenzie failed to deal with a route-one ball, sending Morison clear. He elected to try and lift the ball over Gilks and turned to celebrate thinking his effort would find the net only to see the crossbar come to Blackpool's rescue.
Moments later it was the Tangerines' turn to strike the woodwork, on-loan striker David Goodwillie, without a goal on this side of the border since August 2012, bent the ball against the outside of the post from the edge of the area.
Then, 14 minutes in, the hosts claimed the lead. The returning Tony McMahon's near-post corner found Fuller, who stole a march on his marker to nod in to the ground and over the line.
The relief around Bloomfield Road was palpable yet, three minutes later, the familiar feeling of despair had returned as the Lions won a penalty.
Kirk Broadfoot was caught the wrong side of Morison as an Ed Upson cross came in and bundled the Welshman to the ground inside the six-yard box. Referee Andy Madley immediately pointed to the spot but produced just a caution for the offender.
Morison opted to take the spot-kick himself, however Gilks guessed right, flicking a poor effort away with his legs to preserve Blackpool's lead.
There have been plenty of times in the past four months when Blackpool could justifiably claim luck was against them. However, as Martyn Woolford capitalised on a Broadfoot error to smack another shot against the frame of the goal, there was a sense the tide could finally be turning.
McMahon drilled just over before the break while referee Madley neglected Neal Bishop's strong claim for a Seasiders spot-kick as Ferguson's men entered the break ahead.
A second goal would really have alleviated the pressure on Ferguson's side and, shortly after he had been booked for diving, Goodwillie came close to grabbing one with a placed effort which David Forde did well to palm away.
Chances were largely at a premium, though, with Gilks having nothing to do apart from comfortably catch Paul Robinson's header as the game entered the final 10 minutes.
Shaun Williams curled a free-kick into the stopper's gloves while, at the other end, Goodwillie comically fluffed his lines in front of goal. However, it mattered not as Blackpool's 18-game winless streak finally came to an end with the final whistle greeted by an outpouring of relief from fans and players alike.