Hoxha was born in Gjirokastër, a city in southern Albania (then a part of the Ottoman Empire), the son of Halil Hoxha, a Muslim Tosk cloth merchant who travelled widely across Europe and the United States, and Gjylihan (Gjylo) Hoxha née Çuçi.
The Hoxha family was attached to the Bektashi Order; in 1916 his father brought him to seek the blessing of Baba Selim of the Zall Teqe.
After the maktab, he followed his studies in the city senior high school "Liria". He started his studies at the Gjirokastër Lyceum in 1923. After the lyceum was closed, thanks to the intervention of Eqrem Libohova Hoxha was awarded a state scholarship for the continuation of his studies in Korçë, at the French language Albanian National Lyceum until 1930.
In 1930, Hoxha went to study at the University of Montpellier in France on a state scholarship for the faculty of natural science. He never took an exam staying four years in Montpellier, against the Albanian laws of the time. He never returned the scholarship. He later went to Paris, where he presented himself to anti-Zogist immigrants as the brother-in-law of Bahri Omari.
In the years 1935 to 1936, he was employed as a secretary at the Albanian consulate in Brussels. After returning to Albania, he worked as a contract teacher in the Gymnasium of Tirana. Hoxha taught morals in the Korça Liceum from 1937 to 1939 and also served as the caretaker of the school library.
On 7 April 1939, Albania was invaded by Fascist Italy. The Italians established a puppet government, the Albanian Kingdom (1939–43), under Shefqet Vërlaci. Hoxha was indifferent regarding the invasion.
In the summer of 1939 he went to Italy on vacation. At the end of 1939, he was transferred to the Gjirokastra Gymnasium, but he soon returned to Tirana. He was helped by his best friend, Esat Dishnica, who introduced Hoxha to Dishnica's cousin Ibrahim Biçakçiu. Hoxha started to sleep in Biçakçiu's tobacco factory "Flora", and after a while Dishnica opened a shop with the same name, where Hoxha started to work. He was a sympathizer of Korça's Communist Group.