In the 1930s he studied at a military college in Naples.
From 1937 to 1939 he fought in the Spanish Civil War in the Garibaldi International Brigade.
From 1939 to 1942 he was in an internment camp in France.
Since 1942, Shehu participated in the partisan movement and the work of the Albanian Communist Party. In 1943, he was elected as a candidate member of the Central Committee of the Party. From 1943 to 1944 he was the commander of the 1st partisan brigade. Thereafter, he was a division commander of the National Liberation Army. From 1944 to 1945 he was a member of the Anti-Fascist Council of National Liberation (the provisional government).
During the war, Shehu won a reputation for brutality. On his command most tribal chiefs in the mountains of northern Albania were executed.
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 he became the chief of the general staff. Later, he was also a lieutenant general and a full general.
In 1948, Shehu "expurgated" the party from the element who "tried to separate Albania from the Soviet Union and lead 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. If he had become a serious rival to Hoxha he would have been eliminated.
Since 1948, he was a member of the Central Committee and the Political Bureau (Politburo) of the Central Committee of the Albanian Party of Labour and from 1948 to 1953 he was a secretary of the Central Commitee. He lost the latter position on June 24 when Enver Hoxha gave up the posts of the Minister of Defence and the Minister of Foreign Affairs, remaining the Chairman of the Council of Ministers. Probably Hoxha was not willing to yield too much power to him.
From 1948 to 1954 he was the deputy chairman of the Council of Ministers and the Minister of the Internal Affairs (and the chief of the secret police). From 1954 to 1981 he succeeded Enver Hoxha as the chairman of the Council of Ministers. From 1974 he was also the Minister of People's Defence.
From 1947 Shehu was a deputy of the People's Assembly.
Shehu was held to be Enver Hoxha's right hand man and the second person in Albania. During 40 years Hoxha was Shehu's friend and nearest comrade. Shehu was one of those who prepared the Chinese-Albanian alliance and the break with the Soviet Union (December 1961).
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: "Who disagrees with our leadership in some point, will get a spit into his face, a blow onto his chin, and, if necessary, a bullet into his head."
It is claimed that in 1981 Shehu opposed Enver Hoxha's isolationism. He was accused in being a Yugoslav spy.
On December 17, 1981, he was found dead in his bedroom with a bullet wound to his head. According to the official announcement (December 18), he had committed suicide in 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 Tiranë.
After his death Shehu was claimed to have been an agent of not only the Yugoslav secret services, but also the CIA and the KGB. In Hoxha's book Titoites (1982) several chapters are dedicated to Shehu's denunciation. Shehu disappeared from the official history of Albania.
According to rumours, Shehu was killed on Hoxha's order because he opposed Hoxha's isolationism. There is a version alleging that Hoxha personally murdered him at a gathering of the Political Bureau.
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.