Real included Denis Cheryshev in their starting lineup for their first match of the 2015-16 competition even though he should have been serving a one-match suspension and the Russia forward opened the scoring in a 3-1 victory.
In a nine-page ruling, the RFEF sharply criticised Real, saying they should have been aware of the sanction, and as well as disqualifying the club fined them 6,001 euros ($6,520.69).
Real president Florentino Perez insisted on Thursday the club had not broken the rules, saying neither Cheryshev nor Real were notified he was banned. They said on Friday they would appeal the sanction.
"Real Madrid C.F. reaffirms its reasoning and confirms that it will present the appropriate appeal with the certainty that the final decision will be favourable to the club," they said on their website (www.realmadrid.com).
Already smarting after bitter rivals Barcelona thrashed them 4-0 at the Bernabeu in last month's La Liga 'Clasico', it is another embarrassing setback for the world's richest club by income following their failed attempt to sign Spain goalkeeper David De Gea from Manchester United in the close season.
That deal broke down when the paperwork did not arrive on time to complete, with both clubs blaming each other for the bureaucratic mix-up.
To add to Real's problems, their striker Karim Benzema is under investigation over an alleged attempt to blackmail France team mate Mathieu Valbuena with a sex video.
Plans for an expensive overhaul of the Bernabeu stadium are also on hold due to a legal challenge.
Cheryshev earned a third yellow card, which carries an automatic one-game ban, playing on loan at Villarreal in last season's Cup.
Real took him off at halftime when they apparently realised their error but Cadiz, who play in the same "Segunda B" regional division as Real's B team, filed an official complaint.
"All Cadiz can do is express regret at what happened," the Andalusian club said on their website (www.cadizcf.com) after Friday's decision was announced.
"At no time did this club want to be the protagonist of the King's Cup tie, only part of the celebration the visit of one of the most important teams in world football means for our city," they added.
The return leg was due to be played at Real's Bernabeu stadium on Dec. 16.
Real's next outing is a La Liga game at home to Getafe on Saturday, when anything less than a convincing victory will heap more pressure on coach Rafa Benitez.
Their notoriously demanding fans chanted for Perez to quit during the defeat to Barca but he has refused to bow to their calls and said he has full confidence in Benitez, appointed at the end of last season to replace the sacked Carlo Ancelotti.
Real are third in La Liga after 13 matches, six points behind leaders and champions Barca, and through to the last 16 of the Champions League as group winners.
Image: Denis Cheryshev of Real Madrid.
Photograph: Gonzalo Arroyo Moreno/Getty Images