N.P was established in October 2003 when the non-tribal, essentially middle-class Balochistan National Democratic Party (BNDP) led by Mir Hasil Khan Bizenjo, son of the Baloch nationalist Ghaus Bakhsh Bizenjo, merged with the non-tribal middle-class nationalist party Balochistan National Movement (BNM) led by Dr. Abdul Hayee Baloch. It is considered to be the successor of the Kalat National Party. Abdul Hayee Baloch became the first chairman of the National Party and Mir Hasil Khan Bizenjo became the secretary general of the new party. In 2008, Abdul Malik Baloch was elected as the party president, and is now a member of the Senate of Pakistan.
The party boycotted the 2008 general elections as a protest against the military operation being conducted in the province at the time. However, Sanaullah Zehri and his followers decided to contest elections forming a faction called NP Parliamentarians. As a result, National Party won one provincial assembly seat with Sanuallah Zehri winning PB-33 Khuzdar-I.