In 1871 entered the new Imperial German Navy.
Eight years later he worked under Alfred Tirpitz in the torpedo service, and thereafter received several overseas cruiser commands. In 1889 Müller was first appointed to the Navy Cabinet; two years later he commanded a gunboat in China and in 1895 served Prince Henry as adjutant, accompanying the kaiser's brother to the Far East two years later. At the turn of the century, Captain Müller returned to the Navy Cabinet and was ennobled. In 1902 he commanded the battleship Wettin and, after a brief stint as naval adjutant to Wilhelm II in the grade of rear admiral, was appointed chief of the Navy Cabinet in 1908. Vice Admiral von Müller worked diligently to recruit the officers to staff Tirpitz's rapidly expanding fleet. He campaigned against alcoholism and bachelorhood; his social gatherings (''milk circles") were widely feared by young officers. And to the dismay of most senior admirals, Müller along with the kaiser championed education rather than birth as sole criterion for entrance and promotion in the officer corps. He was promoted admiral in 1910.
At the outbreak of war in August 1914, Müller was calm and resigned. He had long considered war with England as "unavoidable" and considered the timing propitious: "The mood is brilliant." When by Christmas the French had not been overrun and German naval disasters (Helgoland Bight, Falkland, Dogger Bank) increased, Müller grew more pessimistic about the war. Above all, he saw no prospects in a suicide sortie by the numerically inferior High Sea Fleet against the British Grand Fleet, a stance which netted him the disdain of aggressive younger officers and the nickname Rasputin.
Being constantly in the vicinity of the kaiser, Müller was accused by his enemies of surrounding the Supreme War Lord with a Chinese Wall. Nor did Müller's opposition to the introduction of unrestricted submarine warfare throughout the period 1914-1916 endear him to naval hawks. Worse yet, the admiral's turnaround on January 9, 1917, at Pless in supporting the resumption of unrestricted submarine warfare and in convincing Chancellor Theobald von Bethmann Hollweg to support this bold initiative earned Müller the charge of duplicity from opponents of the U-boat gamble. Admirals Reinhard Scheer and Adolf von Trotha as well as Captain Magnus von Levetzow continued to look on the head of the Navy Cabinet with distrust as Müller steadfastly refused to condone an all-out naval engagement with the British in the North Sea. In attempting to maintain a balance between the views of Bethmann Hollweg and Tirpitz, Müller earned the confidence and trust of neither.
Both chancellor and state secretary were removed from office during the course of the war, and the new naval leadership of Scheer, Trotha, and Levetzow agreed in the summer of 1918 to dislodge Müller from the Navy Cabinet. Indeed, after the naval reorganization of August 11, which brought Scheer to power as head of a new Supreme Command of the Navy, Müller was scheduled for retirement and replacement by Trotha as soon as the transition in commands could be completed. Instead, rebellion and revolution in the wake of the planned suicide sortie on October 30, 1918, brought an inglorious end to the Imperial German Navy. Müller retired to Hagelsberg in the Mark to work on his diaries; he died there along the banks of the Spree River on April 19, 1940.