Melissa Parke was born on 11 August 1966 at Bunbury, the eldest of four children of George and Lorraine Parke, apple orchardists in Donnybrook. Her secondary education was undertaken at Donnybrook District High School and Bunbury Senior High School, and as a Rotary exchange student in France for one year.

Melissa then completed one year of Arts at the University of Western Australia before taking a year off university to work. She completed a Bachelor of Business (with Distinction) at Curtin University in 1989. This was followed by a law degree at the University of New South Wales and subsequently in 1998 a Master of Laws (LLM) in Public International Law at Murdoch University where she lectured in 1999.

From 1990 to 1994 Melissa worked in law offices in Sydney and Bunbury and from 1994 to 1997 as solicitor-in–charge at the Bunbury Community Legal Centre. It was during this period that she contested the Legislative Assembly seat of Mitchell for the ALP at the 1996 election.

In 1999 Melissa accepted a job with the United Nations Mission in Kosovo and over the following eight years worked for the UN in Gaza, New York, Beirut and Cyprus. In 2006 she was seconded to establish a new UN ethics office and she also participated in the UN investigation of the assassination of former Lebanese Prime Minister Rafik Hariri.

With the retirement of Carmen Lawrence, Melissa was preselected without opposition as the ALP candidate for the federal Fremantle seat which she won comfortably at the November 2007 federal election. The first parliamentary committees to which she was elected included the Joint Standing Committee on Foreign Affairs, the Joint Standing Committee on Treaties and the Joint Standing Committee on the Australian Commission for Law Enforcement Integrity. She is also the President of the UNICEF Parliamentary Association.

Over the years her community activities have included acting as a Western Australian representative on the Australian Conservation Foundation, president of Labor Lawyers in Western Australia and spokesperson for the Communities for Coastal Conservation. She also served on the management committee of the Waratah Domestic Violence and Sexual Assault Referral Centre.