A court judgement stated that some Māori appeared to have the right to seek formal ownership of a specific portion of seabed in the Marlborough Sounds. This prospect alarmed many sectors of New Zealand society, however, and the Labour Party foreshadowed legislation in favour of state ownership instead. This angered many Māori, including many of Labour's Māori MPs. Two MPs representing Māori seats, Tariana Turia and Nanaia Mahuta, announced an intent to vote against the legislation.
Turia, a junior minister, once informed that voting against the government would appear "incompatible" with holding ministerial rank, announced on April 30 2004 her intention to resign from the Labour Party. Her resignation took effect on May 17, and she left parliament until she won a by-election in her Te Tai Hauauru seat two months later.
After leaving the Labour Party, Turia, subsequently joined by Sharples, began organizing a new political party. They and their supporters agreed that the new organization would simply use the name of "the Māori Party". They chose a logo of black and red — traditional Māori colours — incorporating a koru design, also traditional.
The leaders of the Māori Party have indicated that they wish to unite "all Māori" into a single political movement.
Many of the party's backers believe the Māori Party will come to dominate Māori politics in the same way that Labour traditionally has.
Critics of the new party, however, have dismissed the party's chances of success. John Tamihere, when Associate Minister of Māori Affairs, attacked the Māori Party on a number of issues, painting it as ultimately unviable. One of the main problems for the new party involves the broad range of opinion that the party must represent. Tamihere has also said that the party's leaders "belong to a relatively wealthy, educated élite" whose "reality is considerably removed from the overwhelming majority of Māori." Tamihere claims that Māori have more interest in issues such as health, education, and employment than in the comparatively academic issue of the "foreshore and seabed".
The Māori Party also failed to gain the backing of Ngai Tahu, one of the most influential (and wealthy) iwi. While broadly supporting the party's policy platform, Ngai Tahu said it would not provide financial support or political endorsement to any one party. Chief executive Tahu Potiki said Ngai Tahu would never back any one party over another, including a Māori party, adding: "If you start to play the party game and start talking about loyalties, when they say something dumb, you end up with egg on your face. And it's only a matter of time before they do."
As one of its major problems, the new party faces the challenge of uniting very many diverse views. Māori overall do not hold homogeneous opinions, and finding a balance between radicals, conservatives, and moderates seems likely to prove problematic. Donna Hall (a controversial lawyer) and Titewhai Harawira (a radical activist) both indicated an interest in the party, but the party's leadership showed reluctance to welcome them on board as candidates, apparently judging them too controversial. Tariana Turia, however, believes that the party can achieve unity, and says that in the new Māori Party, "all Māori parties [have] come together in the spirit of unity".
A Marae-Digipoll in April 2005 predicted that the party would have won five of the seven Māori seats if an election had been held the day after the poll.
In the elections, the party won four out of seven Māori seats and 2.12% of the party vote. This entitled the Māori Party to 3 list seats, so the fourth electorate seat became an overhang seat. Tariana Turia held Te Tai Hauauru; Pita Sharples won the Tamaki-Makaurau electorate; Hone Harawira, son of Titewhai Harawira, won Te Tai Tokerau; and Te Ururoa Flavell won Waiariki.
In the post-election period the Māori Party convened a series of hui to decide whether to support Labour or National, though some party leaders have indicated they prefer to deal with Labour. That day, however, Turia and Prime Minister Helen Clark met privately and ruled out a formal coalition. Coupled with the support of the Greens and Progressives, Māori Party support would have given Clark just enough support to govern without the support of other parties. However, in the end, no deal was done and the Māori Party stayed in Opposition, citing that they were not prepared to compromise their positions.
Gerry Brownlee, Deputy Leader of the National Party claimed after the election that both Labour and National could rely on "57 seats" out of the 62 required in the 2005 election to govern. This implied that National had received support from United Future , Act  and the Māori Party  in addition to National's own 49 seats. Brash himself later supported this statement and claimed he had witnesses to it. This came after the National Party tried to woo the Māori Party in attempts to both see if a coalition arrangement was feasible and to counter any attempts which may have been made by Helen Clark. Tariana Turia denied this claim.
However critics said this would have reminded onlookers of how the Māori Party and National were said to be in coalition or confidence and supply talks. This may also have served to reinforce the Labour Party's election campaign statement that a 'vote for the Māori Party is a vote for National'. One Ratana kaumatua (elder) said this was deliberate and deserved after the talks.