Když se rozhodlo o zahájení vývoje typu Constellation, nebyla firma Lockheed významným hráčem v odvětví výroby dopravních letadel. Výraběla jen několik typů jednomotorových dopravních letadel výchazejících z typu Vega a dvoumotorové modely Lockeed 10, 12 a 14. A o všechny tyto typy přestali mít zákazníci zájem, když na trh vstoupil Douglas DC-3. Jednička na poli dopravních letadel, firma Douglas, v té době zahájila také vývoj čtyřmotorového letounu DC-4E vyznačujícím se trojitými svislými ocasními plochami.
Další americký výrobce, firma Boeing, nabízela koncem třicátých let dvacátého století velké létající čluny Boeing 314 Pan Am Clipper a vyvíjela první dopravní letoun s přetlakovou kabinou Boeing 307. Zkušenosti s čtyřmotorovými dopravními letadly (létajícími čluny) měli také Sikorski a Martin, jediný komu chyběly byl Lockheed.
Lockheed v té době pracoval na stíhacím letounu P-38 Lightning a hlídkovém a bombardovacím stroji Hudson vycházejím z dopravního L-14. Vedení Lockheedu se rozhodlo také přiživit rozvoji cestování po Spojených státech a byl zahájen vývoj čtyřmotorového dopravního letadla. Podle prvních plánů se měl na čtyřmotorový pohon předělat a typ L-14, který by také dostal prodloužený trup. Tento projekt byl označen jako L-44 Excalibur. Avšak letecké společnosti neprojevily o Excalibur zájem, oproti konkurenčním letadlům nenabízel nic nového a navíc byl pomalejší a menší.
V létě 1939 tak začala firma Lockheed pracovat na zcela novém typu označeném L-49 Excalibur A, ze kterého se posléze stal typ L-049 Constellation. Nový stroj se vyznačoval netradičním tvarem trupu, křídlo Constellationu bylo zvětšené ze stíhačky P-38. Vztlakové klapky pocházely z typu L-14, pochopitelně patřičně rozměrově upravené. Čtyři motorové gondoly ukrývaly ve své době nejvýkonnější letecké motory Wright R-3350. Konstruktéři dále uvažovali o tzv. kachní konfiguraci, čili umístění stabilizátoru a výškovým kormidlem na příď trupu. To se ale ukázalo jako příliš radikální, potencionální zákazníky to spíš odrazovalo. Nakonec tedy konstruktéři umístili stabilizátor mezi trojité vodorovné ocasní plochy.
Začala ale zuřit 2.světová válka a rozmach letecké dopravy byl rázem tentam. Firma Douglas ukončila vývoj svého čtyřmotorového typu DC-4E a pod označením DC-4 vyvinula nakonec značně jednodušší a menší letoun, který ve velkých počtech, pod označením C-54, kupovalo americké letectvo. Jediný prototyp DC-4E prodal Douglas v roce 1939 japonským aeroliniím Japanese Imperial Airways a posloužil jako základ při vývoji jediného japonského čtyřmotorového bombardéru Nakajima G5N, který ovšem nebyl nikdy použit v boji.
Vypadalo to, že ani druhý Lockheedův projekt čtyřmotorového letounu neopustí kreslící stoly kontruktérů. Zasáhl však miliardář Howard Hughes, majitel letecké společnosti TWA, který tajně objednal 40 kusů nového Constellationu. Lockheed ale musel splnit jeho požadavky na rychlost a výkony nového letounu. Hughes hodlal ohromit konkurenční aerolinky, především pak United Airlines a American Airlines. Po firmě Lockheed chtěl aby vývoj Constellationu držela v utajení a navíc požadoval, aby první 2 roky výroby byly nové letouny dodávány výhradně TWA a žádné jiné letecké společnosti. Když se to později dozvěděli představitelé American Airlines, dušovali se, že již nikdy žádný letoun se značkou Lockheed neobjednají. Vydrželo jim to ale jen do roku 1955, kdy American Airlines objednaly 40 kusů turbovrtulového typu L-188 Electra II.
Úplně prvním uživatelem Constellationů se ale nakonec stala po vstupu USA do války americká armáda, která je zařadila do služby pod označením C-69 jako transportní. Výstřední miliardář Hughes se ale odhodlal k bezpredentnímu kousku. V továrně Lockheed v kalifornském Burbanku si nechal v dubnu 1944 přistavit druhý prototyp Constellationu, v té době už vlastněný armádou, nechal ho narychlo nastříkat do barev TWA a odletěl s ním do Washingtonu. Ustanovil nový rychlostní rekord při přeletu ze západního na východní pobřeží USA, když tuto trať zvládl v čase 6 hodin a 58 minut. Jeho kopilot byl při přeletu Jack Frye, prezident TWA, na palubě byl i šéfkonstruktér Lockheedu, Clarence „Kelly“ Johnson a tehdejší Hughesova přítelkyně, hollywoodská superstar Ava Gardner. Johnson měl dosti pochybnosti o Hughesových pilotních schopnostech a mezi přáteli prohlašoval „ten šílenec nás mohl všechny zabít“.
Na zpáteční cestě do Burbanku přistál Hughes na letišti Wright Field u Daytonu (dnešní letecká základna Wright-Patterson), kde nastoupil první pilot motorového letadla na světě Orville Wright, který si dokonce mohl řízení Constellationu vyzkoušet. Jednalo se ale o dobře promyšlenou reklamu, jinak by Hughes Wrighta jentak nesvezl.
Vývoj a výrobu Constellationů převzala veřejně armáda již v roce 1942 a zhatila Hughesovi plány na tajný vývoj letadla. Viděla v Constellationu letoun schopný přepravit na tehdejší dobu velké množství vojáků na velkou vzdálenost. Počáteční optimismus však záhy zhatily motory Wright R-3350. Byly sice velmi výkonné, ale poruchové a tak armáda nakonec převzala jen 13 Constellationů a prototyp. Její pozornost se naplno obrátila na Douglas C-54, jehož motory Pratt and Whitney R-2000 nabízely sice oproti Wrightům poloviční výkon, ale byly neskonale spolehlivější. Lockheed dostal od americké armády úkol soustředit se na zdokonalování hlídkových a bombardovacích Hudsonů, výrobce motorů Wright měl nadále pracovat na vývoji R-3350, ale přizpůsobit ho pro bombardovací Boeingy B-29.