It would be reviewed after nine months and last no more two years.
The total would be up to 143 New Zealand personnel.
Mr Key was speaking in Parliament to confirm New Zealand's deployment of troop trainers to help Iraq fight Isis (Islamic State) which has taken over parts of Iraq and Syria and conducted barbaric killings.
"This brutal group and its distressing methods deserve the strongest condemnation," Mr Key said.
He said New Zealand did not shy away from its responsibilities when the rule of law was under threat.
If anything Isil's brutality had worsened since his national security speech last November.
Mr Key said the ability of Isis to motivate Islamic radicals threatened the security not just of the Middle East, but regionally and locally.
"New Zealand is a country that stands up for its values. We stand up for what's right.
"We have an obligation to support stability and the rule of law internationally.
"We do not shy away from taking our share of the burden when the international rules-based system is threatened.
"We have carved out our own independent foreign policy over decades and we take pride in it."
Mr Key said force protection would be deployed in Iraq to support New Zealand's trainers.
He said although he had ruled out sending Special Air Service (SAS) troops to Iraq in November, SAS soldiers might be deployed in Iraq "for short periods" to protect the trainers.
Logistics and medical support would also be sent to the Middle East.
"We will secure the best protections we realistically can for our personnel," Mr Key said.
Mr Key said legal protections would be worked through with the Iraqi Government in the coming weeks.
Foreign Minister Murray McCully is expected to visit Baghdad to negotiate an agreement with the Iraqi Government.
Mr Key said New Zealand would appoint a new ambassador on counter-terrorism, mirroring a move announced yesterday by Australian Prime Minister Tony Abbott.
Mr Key last year said there was a watchlist of 35 to 40 New Zealanders "of concern in the foreign fighter context", and they remained under surveillance.
An additional group requiring further investigation was "growing in number".
"We have strengthened the ability of our intelligence agencies to deal with this and they are taking steps to add to their resources.
"We cannot be complacent, as events in Sydney, Paris and Ottawa have underscored."
Mr Key concluded his statement by saying New Zealand did not take its commitment to Iraq lightly.
"In return we expect that the Iraqi Government will make good on its commitment to an inclusive government that treats all Iraqi citizens with respect.
"Sending our forces to Iraq is not an easy decision but it is the right decision. They will go with our best wishes."
Defence Minister Gerry Brownlee said the total estimated cost of a two-year deployment was $65 million, though some costs had not yet been finalised.
He said New Zealand would expand its diplomatic and humanitarian support in Iraq.
As well as appointing a new counter-terrorism ambassador, the Government was looking to base a diplomatic representative in Baghdad to serve as a conduit between the Iraqi Government and New Zealand's military deployment.
New Zealand has committed $14.5 million so far in aid for people displaced by fighting in Iraq and Syria.
Mr McCully confirmed today that $1 million of this total would be used for a pilot programme in Jordan which would provide basic education for 1800 vulnerable young people.
Further options for humanitarian support were also being considered.
In his reply to the Prime Minister's statement, Labour leader Andrew Little said Labour could see no case for sending troops to Iraq.
He said it was clear Islamic State was brutal. "There wouldn't be a New Zealander who has seen those images whose stomachs have not been turned. But let's be clear what we're dealing with. They call themselves, Islamic State, but they are not a state. They run across borders, they are cultural, ethnic, religious and driven by a number of motivations."
He said it was a "depository of the dispossessed, the extreme and yes, the evil, but it is not a conventional enemy''.
Mr Little said it was clear the Government had made its decision some time ago "and I venture to suggest it was taken for a range of reasons that have not been outlined today."
He doubted Mr Key's assurances the training forces would be "behind the wire". He said there was little doubt the troops would be exposed to the wider combat and there was little to gain.
"After 10 years of training of the Iraq Army by the US Army, what impact will we have? What can we hope to achieve? We think be sending a very modest force, we are going to achieve what the US Army has not been able to achieve in 10 years? We will not fix the Iraqi Army. It is broken, it is corrupt."
He said Iraq's foreign minister had told Labour that civil reconstruction was just as critical. "No one will defeat Islamic State through the Iraqi Army." That could only be achieved by turning Iraq into a well-functioning state and developing industries such as agriculture.
"NZ has a reputation abroad as an honest broker. We won [the Security Council seat] because of our reputations as a responsible, reputable global citizen." He said NZ had an opportunity to provide leadership in a way it had not before and should do that in Iraq.
Green Party co-leader Dr Russel Norman said today's announcement "dragged us by the bootlaces" into another Middle East war without a lack of clear goals.
It was a decision made in Washington, not Wellington, he said.
National had prevented Parliament from voting on whether or not the country should go to war, he said.
"It makes no sense to enter a conflict that simply endangers New Zealanders overseas or here...[John Key] does not have a mandate, and he knows it."
Mr Key was behaving as if he headed the 51st state of the United States, Dr Norman said. It was therefore more correct to address the Greens' protests to US president Barack Obama.
Dr Norman said the United States' list of ills in the Middle East was a long one that went some way to explaining the growth of extremism in the region. "Every Western bomb that has been dropped on the Middle East over the last half century...has only added to the ISIL recruitment queue."
Sending New Zealand troops to Iraq would not help in any way, he said, and New Zealand needed to have the courage to tell that to the "head of the club", the United States.
"When it comes to Western military interventions in Iraq, New Zealand and the world have been there and done that. It was a mess."
Dr Norman said the deployment to Afghanistan was put to a vote in Parliament in 2001, and this deployment should be too.
"We correctly stayed out of the 2003 Iraq war. It is ridiculous that 12 years later we are being dragged into its aftermath.
"Not even the Government's support partners think going to war is the answer to the situation in Iraq, yet this is what John Key is willing to do to be 'part of the club'."
Maori Party co-leader Te Ururoa Flavell said his party understood the desire to assist in the fight in Iraq.
There was a large scale humanitarian crisis in the Middle East, and New Zealand had much to contribute - but not by sending our own troops.
The Maori Party believed that sending personnel to train troops was effectively the same as sending troops to participate, and would be regarded as an act of aggression by Isis.
"We are raising our heads effectively above the parapet."
Mr Flavell said today's decision should be put in the context of past conflicts including WWI. Maori had always been prominent in military and peacekeeping missions.
"There are stories of immense valour...there are stories of immense loss."
People had asked him why New Zealand was joining the Iraq campaign, while ignoring the situation in West Papua, a province in Indonesia where many are seeking self-determination, Mr Flavell said.
"Despite our views...we do wish our forces well...they will make us proud. We pray that they will be looked after and return home safe."
United Future leader Peter Dunne also believed the Government was making a mistake, saying it was effectively now committing to a much longer-term engagement than the two years set out.
His concern about deploying almost 150 troops was escalation of the conflict. "It is very difficult to control these sorts of incursions, to protect just the goal we had to start with."
He said Islamic State was unlikely to distinguish between combat soldiers and trainers.
He also doubted it would be over within two years. "We are committing NZ personnel for what will be a long-term engagement and we have to face the consequences of that."
Mr Dunne said in the history of engagement in the Middle East the one constant was that external intervention had invariably resulted in failure. The consequence of that was the very disillusionment that resulted in extremism.
"The question is not whether we should do anything, but what can we do constructively. We might feel good about making a contribution, but we will not change anything."
Mr Dunne said the same points had been raised in New Zealand through successive debates on war, including in Iraq and Afghanistan. "We should be using our role on the Security Council to ensure any action which takes place against ISIL is UN-mandated."
The push to stop Isis: Timeline
2014
June 9: Islamic State secures a major stronghold by capturing Mosul, Iraq's second-largest city.
June 18: PM John Key says NZ's only contribution to Iraq will be humanitarian aid, and rules out deployment of SAS troops.
August 7: US President authorises airstrikes against ISIS, beginning in northern Iraq.
September 12: Australian PM Tony Abbott raises terror threat level from "medium" to "high" out of concern about domestic terror attacks.
September 29: PM John Key says he cannot rule out NZ support for fight against Islamic State after the US names NZ as part of a 60-country coalition. Key says combat troops are unlikely.
October 6: Australia joins fight against Islamic State with airstrikes in northern Iraq.
October 13: New Zealand raises terror threat level from "very low" to "low" in response to threat of foreign fighters returning to NZ to carry out terror attacks. Govt announces review of intelligence and security legislation.
November 5: In a major speech on security, PM John Key reveals 80 New Zealanders are linked to the Islamic State, 40 of whom are being closely watched. He outlines new anti-terrorism measures including warrantless surveillance and greater powers to cancel passports. Key also says 100 military trainers could be sent to Iraq.
December 9: Anti-terror law changes passed under urgency, with some amendments after widespread protest from Opposition parties, experts and NGOs.
2015
January 25: PM John Key tells BBC that NZ's likely military contribution to the fight against Islamic State "is the price of the club" that NZ belongs to with the US, Australia, Britain and Canada.
February 4: During a visit to NZ, British foreign secretary Philip Hammond says NZ is regarded as family and he hopes it will become actively involved in the fight against the Islamic State.
February 10: Defence Minister Gerry Brownlee gives the Defence Force the go-ahead to begin training for likely deployment to Iraq.
February 13: Iraqi foreign minister Ibrahim al-Ja'afari travels to New Zealand to ask for international support in the fight against the Islamic State.
February 24: PM John Key confirms deployment of military trainers to Iraq.
- NZ Herald
