It's is explained in the first "Dune" book that the Harkonnens have had the stewardship of Arrakis for 80 years before handing it over to the Atreides but who had the 'fief' before them?
Assuming you consider the prequel books by Herbert's son to be canon, the answer is that the fiefdom of Arrakis was previously held by House Richese.
"As our ambassador has explained repeatedly to your emissaries," Calimar added.
"Since my House lost control of the spice operations on Arrakis -- you replaced us, don't forget -- we have attempted to rebuild our economic foundation." The Premier held his chin high, pretending that he still had some pride left.
"Initially, the downfall of Ix was a boon to us, removing competition. However, our finances remain somewhat . . . strained."
The Baron's spider-black eyes flashed, relishing Calimar's embarrassment. House Richese, manufacturers of exotic weaponry and complex machines, experts in miniaturization and Richesian mirrors, had made initial market-share gains against rival Ixian companies during the upheavals on Ix.