Mediaworks, the owners of TV3, confirmed it had fired Kills and Moon just hours before the pair were due to feature on tonight's live elimination show.
It is understood the media company had come under extreme pressure from sponsors and fellow judges Stan Walker and Melanie Blatt to take action.
In a statement to 3News, Mediaworks chief executive Mark Weldon said: "Last night on X Factor both Kills and Moon made comments that were completely unacceptable.
"While the judges on X Factor are expected to provide critiques of the performances, we will not tolerate such destructive tirades from any of the judges," he said.
"Contestants put their all into this competition and they should expect to receive feedback and criticism that is professional and constructive. We no longer have confidence that Kills and Moon are the right people to perform the role of X Factor judges and they will leave the show, effective immediately."
Tonight's live show will be judged by Walker and Blatt, with two new judges to be announced this week.
The owner of the X Factor franchise, FremantleMedia, said the judges had shown "very poor judgement and intention".
"We 100 percent support TV3 and MediaWorks in their decision to remove them. The X Factor does not tolerate the behaviour they displayed last night," a spokesman said.
X Factor executive producer Andrew Szusterman said: "We have reacted decisively and in the best interests of the contestants. We now need to move on and give the contestants and the public the competition they deserve."
TV3 had come under huge pressure after Kills and Moon humiliated contestant Joe Irvine last night and called him "disgusting" and "creepy".
Kills accused Irvine of copying her husband, fellow judge Willy Moon, "from the hair to the suit", and said he was a "laughing stock" and made her "sick". Moon added that Irvine reminded him of a creepy killer and found his performance of Cry Me a River "cheap and absurd".
McDonald's said this morning the comments made by Kills and Moon were unacceptable. "We have spoken to MediaWorks [the owners of TV3] regarding the incident involving Natalia Kills and Willy Moon, to make it clear that we believe the comments made were wholly unacceptable."
2Degrees said it viewed the incident "very seriously".
Judi Clements, chief executive of Mental Health Foundation, criticised the show, saying the comments by Kills and Moon "encouraged bullying, demeaning behaviour".
"We all have the responsibility to treat people with dignity and respect and not be cruel and hurtful. It's not about special treatment [for anyone suffering mental illness or depression].
"There is an issue about how this behaviour affects young people, in particular... It's the glorification of bullying behaviour."
TV3 chiefs also came under fire from New Zealand on Air, which has given X Factor $800,000 of funding. It said: "We have advised TV3 we are disappointed that the focus has been taken off the music. We do not condone bullying."
The controversy comes as audience numbers for the show continue to fall. Just 256,000 people tuned in to watch last night's episode, down on previous weeks. Earlier in the season, ratings were consistently above 300,000 per episode.
Both Moon and Kills were heavily criticised on social media for their treatment of Irvine, with Blatt and Walker chiding Kills and saying the situation was out of control.
Walker, who has fronted anti-bullying campaigns, tweeted: "Im sooooo sorry for any offence tonight... Things got real heated & a lil out of control but Joe is allgood, hes the man...."
He also cautioned his followers not to bully Kills and Moon over the incident: "There is a time and place for everything. For ME it ain't on TV. I am completely against bullying, but fighting fire with fire ain't the way."
This morning he posted on Facebook: "It's out of control now... We're better than that... Justice will prevail... Dont attck her cos ur just falling in2 her trap. Then u become the bully... Dont exalt her by insulting her cos u are making her more famous... Like i kinda am now lol... Aaaarrrgg this is stressful... God bless everyone.... Peace & harmony yall..."
He added: "Everyone, even tho she is in the wrong, 2 wrongs dont make a right, dont attack her & lower urselves 2 be like that. This is out of control!"
Blatt tweeted last night: "I quite obvs am not cool with what went down last night but remember 2 wrongs do not make a right. whatever the reason or outlet you use."
She tweeted this morning: "I've tried to keep my cool and stay professional but really @nataliakills? Sorry love, you';re a t***."
Mr Irvine responded to the incident, tweeting this morning: ''In the words of Lili last night why you gotta be so rude don't you know I'm human too''
Kills and Moon have not responded directly to the accusations, but have been active on social media.
Kills tweeted this morning: "I love you guys, thanks for your support & understanding my passionate opinions! You know what they say about me .." She included a link to an explicit video of her song Problem.
Last night she tweeted: "Had the most fun at the live shows tonight! So many new followers! Love you all - time to celebrate!" She also wrote "love you baby" to Moon and posted a link a picture of actors Woody Harrelson and Juliette Lewis in the controversial 1994 Quentin Tarantino film Natural Born Killers.
TV3 had earlier issued a statement on Facebook, saying it did not condone bullying. "Following tonight's episode of The X Factor NZ we received a huge amount of feedback about comments made by our judges. The nature of live television can be unpredictable and we appreciate you taking the time to voice your opinion. TV3 does not condone bullying and are currently on-site with Joe who is doing well," it said.
A petition on Change.org asked for Kills to be removed as a judge from the show has more than 21,000 supporters and Family First called for a boycott of the show.
X Factor viewers, including some past contestants, also criticised Kills, with the hashtag #xfactornz trending on Twitter after the show. Last season's runner-up, Benny Tipene, said he was "gutted that I went back on the show now eh. Especially with someone so heartless. F*** that feedback."
Even All Black Israel Dagg weighed in: ''Those comments were inappropriate and disgraceful..''
Irvine himself tweeted he had "survived the Kills!"
The network's handling of the X Factor franchise is being closely scrutinised by owners FremantleMedia and Simon Cowell, who have already warned TV3 producers about bringing the show into disrepute.
In her judgment of Irvine's performance, Kills said: "As an artist who respects creative integrity and intellectual property, I am disgusted at how much you have copied my husband, from the hair to the suit," Kills said. "Do you not have any value or respect for originality?
"You're a laughing stock. It's cheesy, it's disgusting, I personally found it absolutely artistically atrocious. I am embarrassed to be sitting here in your presence having to even dignify you with an answer of my opinion ... it's disgusting, you make me sick ... I'm ashamed to even be here."
Moon, who hit headlines over the weekend for allegedly swearing at an Auckland mother in a bakery, continued the criticism. "To me, it just feels a little bit cheap and absurd," he said of the performance.
Moon said Irvine reminded him of Psycho killer Norman Bates: "It's just a little bit creepy ... I feel like you're going to stitch someone's skin to your face and then kill everyone in the audience."
TV3 faces questions over its handling of the X Factor franchise and its reality TV stable. Last month TV3 was at the centre of a media storm for minimising the role an X Factor contestant played in the manslaughter of a teenager in 2004. And on Friday it came under fire over revelations one of the contestants on The Bachelor NZ was sentenced to 18 months' jail for stealing almost $40,000 from her employer.
Moon and Kills have caused headaches for TV3 outside the X Factor. Last week Moon abused an Auckland mother at a bakery, hissing the C-word at her in front of customers and staff.
X Factor producers TV3 issued an apology on Moon's behalf on Friday, saying he regretted the incident and his language, but Moon said at the weekend he was not sorry, and accused the woman, Tracey Neal-Gailer, of lying.
Television commentator and founder of throng.co.nz Regan Cunliffe says the ratings for X Factor are "not great" particularly when compared to the first season.
Numbers dropped significantly following the Shae Brider controversy, however, Cunliffe says that was part of a wider trend, which sees viewer numbers drop off after the audition rounds. "I don't think Shae Brider in itself had an impact on the ratings," he says. "But the problem they have is all these things start to mount up."
Cunliffe was in the live studio audience last night when Kills made her comments to Irvine but says, at first, the audience didn't realise she was condemning him.
"The strange thing is you can't see the judges' faces ... She starts talking and half the audience went 'yeah' and cheered. All of a sudden, it was like, 'where the hell is she going with this?'. Very quickly, the audience turned. There was certainly a sense of shock."
Cunliffe said he was disappointed by the outburst and the fact it has diverted attention from other contestants' performances. "Once again, here we are all talking about the judges. 13 acts are trying to make a career for themselves. Who's talking about them today?"
Cunliffe said it would be interesting to see tonight's ratings and whether people tuned in to see how producers respond to the incident or if the public have turned against Kills and Moon's personalities and refuse to watch.
TV3's handling of X Factor is being closely scrutinsed by FremantleMedia and Cowell's company, Syco Entertainment, which own the format. A clause in the contract stipulates the show can't be brought into disrepute.
Last month Cowell and Freemantle Media blamed TV3 producers for "a very poor editorial decision" for allowing a convicted killer on the show.
They said they had had serious discussions with TV3 about contestant Brider, and said "a more rigid approval process" has been introduced so that it wouldn't happen again.
Brider was sentenced to eight years' jail for his part in the manslaughter of 16-year-old Jeremy Frew in Wanganui in 2004, and in a segment aired on X Factor last week admitted on air that he was involved in a fatal stabbing and described the crime as "a commotion".
However, the victim's mother says Brider did not tell the whole truth in the segment and lashed out at TV3 for not warning her of Brider's appearance.
A clause in the contract held by Syco Entertainment and FremantleMedia stipulates the show cannot be brought into disrepute in accordance with the third-party license agreement. It is understood that special dispensation would have needed to be sought to use Brider, and MediaWorks failed to get permission.
