Sofoulis was born in 1860 in Vathy of Samos, then an autonomous principality under Ottoman suzerainty. His father was Panagiotis Sofoulis, who had fought for the autonomy of the island. Sofoulis studied in the faculty of philosophy of the National and Kapodistrian University of Athens and then in Germany, where he specialised in archaeology. As an archaeologist he published certain insightful surveys and he participated actively in various excavations around Greece.
In 1900 he abandoned archaeological excavations and he was elected a deputy for Samos, being the leader of his own radical faction, which was fighting for the political freedoms of Samos, as stipulated by the Treaty of Autonomy of 1832. Soon, Sofoulis established himself as the head of the Progressives, who favoured reforms and union with the Kingdom of Greece. In 1902, he was elected president of the Samian parliament, effectively Prime Minister of the island.
Pro-Greek agitation and the reaction of the pro-autonomy faction led to increased tensions, and in May 1908 the Prince, Andreas Kopasis Omoudopoulos, asked for the intervention of the Turkish military. The ensuing riots left several dead and Sofoulis was forced to flee to Greece. With the outbreak of the First Balkan War, Sofoulis landed on the island with a group of exiled Samians and swiftly took control: the Ottoman garrison withdrew to Anatolia, and on 11/24 November 1912, the island's parliament officially declared union with Greece.
The unification took place officially on 2 March 1913. Sofoulis remained for a while as the president of the interim government of Samos until April 1914, when he was appointed Governor General of Macedonia. He remained in Thessaloniki until February 1915 when he resigned following the resignation of Eleftherios Venizelos as Prime Minister after a bitter dispute with King Constantine I.
Sofoulis was first elected a deputy to the Hellenic Parliament in the elections of May 1915. He also served as Interior Minister in Venizelos' National Defence government in Thessaloniki, during the National Schism. After the exile of Constantine I, Eleftherios Venizelos and his government returned to Athens, where Sofoulis was elected speaker of the Parliament. He held his post until 1920.