Nicolai was the son of a Prussian Army captain and a farmer's daughter in Braunschweig. In 1893, he selected a military career. He studied from 1901 to 1904 at the War Academy in Berlin. Shortly before his appointment as Chief of the Intelligence Service of the German High Command, he is known to have taken trips to Russian Empire and spoke fluent Russian. Nicolai was a German nationalist and a monarchist, but otherwise considered to be apolitical.^[3]

In 1906, Nicolai began his career in Abteilung IIIb and took command over the East Prussian news station in Königsberg.^[4] He built up the news station in Königsberg to a major centre for espionage against the Russian Empire. After two years of service in early 1913, he was named the head of Abteilung IIIb, which helped to inform the Austro-Hungarian Army that Colonel and Evidenzbureau chief Alfred Redl was a Russian mole.

Nicolai led the German secret service between 1913 and 1919 and directed Abteilung IIIb intensively during the First World War. He wrote, "Before each new acquisition, delivery pp. to ask the I.O., what benefits it brings for the war".^[5]

Information about Nicolai's employment of Mata Hari (7 August 1876 – 15 October 1917) can to be found in the so-called Gempp Report, which became public only in the 1970s.^[6] The papers also contain information from former officers of Abteilung III b about the "Agent H 21", who was Mata Hari. The papers prove that she had entered the service of the German Secret Service in late Autumn 1915. In May 1916, IIIb chief Nicolai had her asked to come to Cologne. After a conversation there, he decided to have her trained as an agent and assigned Major Röpell as her handler. Röpell had taught her "on long walks on the outskirts of the city the basics of the agent's job", and an expert in cipher writing practiced "chemical writing" with her. The "training" took seven days. Mata Hari's mission was to reconnoiter the Third French Republic next offensive plans from Paris, travel through militarily interesting-areas of France and maintain contact with the Kriegsnachrichtenstelle (War Intelligence Office) West in Düsseldorf, whose director was Major Röpell, and the agent headquarters in the German embassy in Madrid, whose director was the military attaché Major Arnold Kalle. Mata Hari was later reasssigned to Captain Hoffmann, who gave her the codename H 21.^[7]

In January 1917, Major Kalle transmitted radio messages to Berlin that described the helpful activities of a German spy codenamed H-21 whose biography so closely matched Mata Hari's that it was patently obvious that she had to be the agent.^[8] The Deuxième Bureau intercepted the messages, and from their content, identified H-21 as Mata Hari. The messages were in a code that German intelligence knew to have been broken by the French, which suggests that the messages were intended to cause Mata Hari to be arrested by the French military.^[9] In early 1917, Colonel Nicolai had grown very annoyed that Mata Hari had provided him with no intelligence worthy of the name, but only Paris gossip about the sex lives of French politicians and Generals. He allegedly decided to terminate her employment by covertly exposing her to the French.^[10]

Another famous female spy that Nicolai was assigned to was Elsbeth Schragmüller. For many years, she was invariably known as Mademoiselle Docteur or Fräulein Doktor, her actual name being revealed only in 1945 from German intelligence documents captured by the Allies after the Second World War. In 1915, Nicolai, assigned her as the chief of the Kriegsnachrichtenstelle Antwerpen.^[11]

When Erich Ludendorff became first quartermaster general at the end of August 1916, there was an expansion of military intelligence for the military police. Nicolai saw himself as having a relentless will to win and as being a military educator, a supervisor and an initiator of patriotic self-discipline. His officers took part in the promotional work for war bonds, and he helped to found the pro-war and militarist German Fatherland Party.

After the end of World War I, Nicolai retired as a colonel. His deputy and then successor in 1920 was Major Friedrich Gempp. Nicolai published two postwar books about his activities.

He was contacted and summoned to Turkey by the Turkish Ministry of Foreign Affairs in 1925, helped founding of National Security Service in 1926 and lectured Turkish officers on intelligence.^[12]

Under Nazi Germany, he belonged to the expert advisory board of the Imperial Institute for the History of the New Germany.^[13]

After the Second World War, Nicolai was arrested by the Soviet SMERSH under the personal order of Stalin,^[14] deported from Germany and interrogated in Moscow. He died in custody on 4 May 1947 in the hospital of Moscow's Butyrka Prison. His body was cremated and buried at the necropolis of the Donskoy Monastery in a mass grave. It was only in 1999 that Russian military prosecutors formally exonerated Nicolai of all charges.^[15]

• Höhne, Heinz; Zolling, Hermann (1972) [1971 (German edition)]. The General Was a Spy. Translated by Martin Sicker and Warburg Limited. New York: Coward, McCann & Geoghegan. (Published in Germany as Pullach Intern, 1971, Hoffman and Campe Verlag, Hamburg.)