The Spaniard was dismissed with four games to go after just 10 weeks in charge, with the club outside the relegation zone only on goal difference.
Allardyce, 68, is Leeds' third permanent manager of a turbulent season -- Gracia replaced Jesse Marsch in February, while director of football Victor Orta left Elland Road by mutual consent on Tuesday.
"We thank Javi and his team for their efforts under difficult circumstances," the club said in a statement.
"The remaining four games of the season will be overseen by experienced head coach Sam Allardyce."
The former Bolton, Newcastle, West Ham and England boss has been out of work since the end of the 2020/21 season after failing to save West Brom from top-flight relegation.
He said it was a "shock" to get the call from Leeds but he had no hesitation in agreeing to join the club, who returned to the top flight in 2020 under Marcelo Bielsa.
Allardyce is reported to have agreed a basic salary of £500,000 ($625,000) for his four games in charge, with a £2.5 million bonus if he can keep Leeds up.
He told his first press conference as manager that taking the job was probably his "biggest challenge" due to the short timescale.
Leeds travel to title-chasing Manchester City on Saturday, before hosting third-placed Newcastle. A trip to West Ham and an Elland Road encounter with European hopefuls Tottenham round out the season.
Allardyce admitted the fixtures were tough, joking: "We start with an easy one on Saturday. Can't get any easier than Manchester City away, can it?"
The Englishman, relegated from the top flight for the first time in his 30-year managerial career at West Brom, firmly stated his credentials.
"Far too many people think that I am old and antiquated, which is so far from the truth," he said.
"I might be 68 and look old, but there's nobody ahead of me in football terms. Not (Manchester City boss) Pep, not (Liverpool manager) Klopp, not (Arsenal's Mikel) Arteta.
"It's all there with me and I share it with them. They do what they do, I do what I do. In terms of knowledge and depth of knowledge, I'm up there with them. I'm not saying I'm better than them, but certainly as good as they are.
"I just wish that sometimes you can get the opportunity that you can show it but that's never going to happen for me now apart from keep Leeds up and if I stayed at Leeds this club was big enough to build a team that was going to challenge those boys eventually.
"But that's a long story away."
Gracia collected 10 points from his first six games in charge but a terrible run of results last month sent Leeds into a downward spiral.
Sunday's 4-1 defeat at Bournemouth followed 4-1, 5-1 and 6-1 defeats to Arsenal, Crystal Palace and Liverpool.
The 23 goals Leeds conceded during April is a Premier League record for a single month.
Gracia's dismissal means there have been 15 managerial changes in the Premier League this season -- five more than in any other previous campaign.
Leeds are the fourth top-flight side to have parted ways with two managers this season.
Former Watford boss Gracia issued a statement in which he said he was "grateful for the opportunity and proud of the team" after a "very intense period".
Despite his impressive record as a club manager, Allardyce lasted only 67 days and one match as England boss before being forced out after a newspaper sting in 2016.
He was asked whether he could be at Elland Road beyond the end of the season.
"Never say never," he said. "It depends what happens at the end of the four matches... and how I feel."
(For more sports news and updates, follow Ahram Online Sports on Twitter at @AO_Sports and on Facebook at AhramOnlineSports.)