The CPP was founded in Calcutta, Union of India on March 6, 1948. A decision was taken at the Second All-India Conference of the Communist Party of India, which was held in Calcutta at that time, that a separate communist party ought to be created in the new state of Pakistan. It was thought that Pakistan, being a relatively small country (in comparison to India) and suffering from instability, was ripe for revolution. The delegates from Pakistan separated themselves and held a separate session where they constituted the CPP. Sajjad Zaheer (founder of the All-India Progressive Writers Association), from West Pakistan, was elected General-Secretary. The delegates from East Pakistan elected an East Pakistan Provincial Committee. Many Muslim leaders of the CPI were sent to Pakistan to help with the formation of the party.
The attempt to start a revolution in Pakistan failed and the CPP leaders were jailed. In the 1951 Rawalpindi Conspiracy Case, many leading members were convicted and the party was forcibly repressed by successive governments.
Diplomatic intervention by Jawaharlal Nehru led to the most prominent CPP leaders being freed and sent back to India. At this stage the CPP was in poor shape in West Pakistan, while in East Pakistan the party had a limited foundation. However, it was difficult to have a unified underground political organization spanning such a vast geographical territory and the East Pakistan branch was able to operate with autonomy.
In the provincial elections in East Pakistan in 1954, the CPP supported the United Front launched by the Awami League, Krishak Praja Party and the Nizam-e-Islam party. Four out of ten CPP candidates were elected, and 23 CPP members were elected as candidates of other parties.
In 1954 the party and its front organizations such as the National Students Federation, Progressive Writers' Movement and Railway Worker’s Union were banned. As a result, the CPP launched the Azad Pakistan Party (APP) in West Pakistan with Mian Iftikhar-ud-Din as leader. In 1957, the CPP and other leftists created the National Awami Party as a legal party. The APP merged into the NAP.