Shehu was born in Çorrush, Mallakastër District, southern Albania, in the family of a Tosk Muslim Imam. He graduated in 1932 at the Tirana Albanian Vocational High School funded by the American Red Cross. His focus was on agriculture. Unsuccessful in finding employment within the Ministry of Agriculture he managed to get a scholarship to attend the Nunziatella military academy of Naples, Italy. After being expelled from this school for his pro-Communist sympathies in 1936 he gained entry to the Tirana Officers School, but he left the following year after volunteering to fight for the republican side in the Spanish Civil War. He joined the Spanish Communist Party and rose to the command of the Fourth Battalion of the XIIth Garibaldi Brigade. After the defeat of the Republican forces he was arrested in France in early 1939 as he was retreating from Spain along with his friends. He was imprisoned in an internment camp in France and later was transferred to an Italian internment camp, where he joined the Italian Communist Party.
In 1942 he returned to Albania, which was under Italian occupation, where he immediately joined the Albanian Communist Party and the Albanian resistance. In 1943, he was elected as a candidate member of the Central Committee of the Communist Party. In August 1943, due to his military experience, he rose swiftly to commander of the 1st Partisan Assault Brigade. Thereafter, he was the commander of 1st Partisan Assault Division of the National Liberation Army. From 1944 to 1945 he was a member of the Anti-Fascist Council of National Liberation (the provisional government).
After Albania was liberated from the German occupation (November 1944), Shehu became the deputy chief of the general staff and, after he studied in Moscow, became the chief of the general staff. Later, he was also a lieutenant general and a full general.
In 1948, Shehu "expurgated" from the party the element who "tried to separate Albania from the Soviet Union and lead her under Belgrade's influence". This made him the nearest person to Enver Hoxha and brought him high offices. However, he remained in Hoxha's shadow.
From 1948, he was a member of the Central Committee and the Politburo of the Party of Labour of Albania, and, from 1948 to 1953, he was a secretary of the Central Committee. He lost the latter position on June 24 when Enver Hoxha gave up the posts of Minister of Defence and Minister of Foreign Affairs while retaining the premiership. Hoxha was probably not willing to yield too much power to him.
From 1948 to 1954 he was deputy prime minister (deputy chairman of the Council of Ministers) and Minister of Internal Affairs. The latter post made him commander of the secret police, the Sigurimi. In 1954, he succeeded Hoxha as Prime Minister. From 1974 he was also the Minister of People's Defence while from 1947 to his death he was a deputy of the People's Assembly.
During the war, Shehu won a reputation for brutality. On his command most clan chiefs in the mountains of northern Albania were executed. In 1949, he ordered 14 Catholic tribesmen in the Mirdita region executed after underground fighters aligned with conservative Albanian political exiles working as Italian Navy espionage agents executed Bardhok Biba, a relative of Catholic tribal leader Gjon Markagjoni who had turned against the tribal system to become a ranking Communist district official. Mike Burke, the American spymaster who set up a 1950 paramilitary project to destabilize and oust the Albanian government, said in 1986 that Shehu was "one tough son of a bitch", whose security forces gave U.S. agents "a tough time".
At the 22nd Congress of the Communist Party of the Soviet Union (October 1961) Anastas Mikoyan, one of the Soviet leaders, quoted Mehmet Shehu, who had said at an Albanian Party Congress: "Whoever disagrees with our leadership in any respect, will get spat in the face, punched on the chin, and, if necessary, a bullet in his head."
Shehu was considered Enver Hoxha's right-hand man and the second most powerful man in Albania. For 40 years Hoxha was Shehu's friend and closest comrade. Shehu was one of those who prepared the Chinese-Albanian alliance and the break with the Soviet Union (December 1961).
On December 17, 1981, he was found dead in his bedroom in Tirana with a bullet wound to his head. According to the official announcement (December 18), he had committed suicide after suffering a nervous breakdown. This was a crime under Albanian law. Shehu was declared to be a "people's enemy" and was buried in a wasteland near the village of Ndroq near Tirana. Shehu's son later launched a campaign to prove that his father had, in fact, been murdered. Reportedly, Shehu had begun speaking out against Hoxha's isolationism.
After his death Shehu was claimed to have been a spy not only for Yugoslavia, but also for the CIA and the KGB. In Hoxha's book Titoites (1982) several chapters are dedicated to Shehu's denunciation. In 1982, the communist party issued a second edition of its official history, removing all references to Shehu. Shehu's widow Fiqerete (born Sanxhaktari) and two of his sons were arrested without any explanation and later imprisoned on different pretexts.
After the fall of Communism and his release from prison in 1991, Mehmet Shehu's younger son Bashkim started seeking his father's remains. On November 19, 2001, it was announced that Mehmet Shehu's remains had been found.
A fictionalised account of Mehmet Shehu's fall and death is the subject of Ismail Kadare's novel The Successor (2003).