Bolo jedno z prvých, ktoré sa v rámci aliancie vytvorilo ešte v decembri 1950 a od počiatku bolo budované prednostne úplne v súlade so zásadnou strategickou líniou aliancie. Vtedajšia situácia v rozdelenej Európe, keď sa hrozba premeny studenej vojny na horúcu stávala veľmi aktuálnou, urýchľovala výstavbu štruktúry tohto veľkého armádneho celku. Veliteľstvo teritoriálne pokrýva územie všetkých európskych členských štátov vrátane priľahlých ostrovov. Rozprestiera sa severojužným smerom od severných výbežkov Nórska až po severný okraj Afriky a od východnej časti atlantického pobrežia až po východné hranice Turecka.
Na čele veliteľstva stojí hlavný veliteľ spojených ozbrojených síl v Európe, ktorým je vždy americký generál s rozsiahlymi právomocami. Výkon jeho funkcie nie je časovo obmedzený. Oficiálne zodpovedá za obranu členských štátov v podradenej oblasti. K jeho hlavným povinnostiam v čase mieru patrí zabezpečenie organizácie, výzbroje a výcviku vojsk vyčlenených v prípade potreby do jeho podriadenosti.
V čase mieru má právo obracať sa priamo na náčelníka generálneho štábu alebo ministra obrany ktoréhokoľvek členského štátu a prerokovať s ním najdôležitejšie vojenské otázky. Jednotlivé krajiny majú v jeho štábe tzv. národného armádneho predstaviteľa. Francúzi sú zastúpení prostredníctvom svojej vojenskej misie pri medzinárodnom štábe NATO.
Hlavnému veliteľovi spojeneckých ozbrojených síl v Európe sú podradené všetky veliteľstvá aliancie v európskom priestore.
Funkciu prvého hlavného veliteľa vykonával generál Dwight Eisenhower (19. 12. 1950 –28. 4. 1952). Jeho voľba na tento post nebola náhodná. Bol totiž stále najpopulárnejšou vojenskou osobnosťou v USA aj v západnej Európe. Preslávil sa ako hlavný veliteľ spojeneckých expedičných síl v druhej svetovej vojne a jeho meno je nerozlučne späté s inváziou zo 6. 6. 1944, ktorou sa v Normandii otvoril druhý front. Práve jeho osobnosť v čase silnej studenej vojny dávala záruku, že novovytváraná aliancia a jej vojenská zložka splní úlohy, ktoré sa od nej čakajú. Generál Eisenhower prestal vykonávať túto funkciu po tom, čo prijal ponuku Republikánskej strany, aby sa ako jej kandidát uchádzal o funkciu prezidenta USA. Bol do nej zvolený 4. novembra 1952 a vykonával ju dve volebné obdobia až do januára 1961.
Aj ďalší Eisenhowerovi nástupcovia, ako aj britskí, francúzski a ďalší generáli zastávajúci v tom čase veliteľské funkcie na rôznych stupňoch štruktúry NATO, boli osobnosti, ktoré sa preslávili na bojiskách druhej svetovej vojny.