Im September 1905 trat Fellgiebel als Fahnenjunker in das Telegraphen-Bataillon Nr. 2 der preußischen Armee ein und begann damit seine militärische Laufbahn. Während des Ersten Weltkrieges war er im Generalstab tätig. Nach Kriegsende erfolgt seine Übernahme in die Reichswehr und Fellgiebel kam als Generalstabsoffizier nach Berlin. Er absolvierte die Stabsoffizierslaufbahn und wurde am 1. April 1928 zum Major befördert. 1933 erfolgte die Beförderung zum Oberstleutnant, 1934 zum Oberst und 1938 die Ernennung zum Generalmajor. Im August 1938 wurde er zum Chef des Heeresnachrichtenwesens und zum Chef der Wehrmachtnachrichtenverbindungen zum Oberkommando der Wehrmacht ernannt und 1940 zum General der Nachrichtentruppe befördert.
Durch die Bekanntschaft mit Generaloberst Ludwig Beck, der sein Vorgesetzter war, und dessen Nachfolger Generaloberst Franz Halder kam Fellgiebel mit den militärischen Widerstandskreisen in Kontakt. Fellgiebel war maßgeblich an der Vorbereitung der Operation Walküre beteiligt und versuchte am Tag des Anschlages auf Adolf Hitler, dem 20. Juli 1944, das Führerhauptquartier von allen Nachrichtenverbindungen abzuschneiden, was ihm jedoch nicht vollständig gelang. Als gegen 13:30 Uhr feststand, dass das Attentat auf Hitler misslungen war und dieser überlebt hatte, musste Fellgiebel die Nachrichtensperre aufheben. In der Absicht den Putsch abzubrechen, sandte er aus der Wolfsschanze eine mehrdeutige Nachricht an die auf den Attentäter Stauffenberg in der Berliner Bendlerstrasse wartenden Putschisten, die daraufhin den Walküreplan zum Teil nicht und zum anderen Teil nicht vollständig auslösten: „Es ist etwas Furchtbares passiert, der Führer lebt“.
Noch am 20. Juli 1944 wurde Fellgiebel in der Wolfsschanze verhaftet. Es folgte eine Anklage vor dem Volksgerichtshof, wo er durch Roland Freisler am 10. August 1944 für schuldig befunden und zum Tode verurteilt wurde. Am 4. September 1944 wurde Fellgiebel im Strafgefängnis Berlin-Plötzensee hingerichtet.[1]