Samotné jméno Praha vyvolává nejvíce diskuzí, které zřejmě nebudou nikdy uzavřeny. Různé hypotézy jsou obvykle zdůvodňovány jazykovědnými konstrukcemi nebo archeologickými nálezy.
Název se běžně odvozuje od slova práh. Podle této nejuznávanější teorie je Praha pojmenována po říčním prahu, tj. brodu, který se nacházel někde pod dnešním Karlovým mostem. Přes tento brod přecházeli lidé přes řeku. Protože se město začalo rozrůstat právě nad tímto brodem, tedy prahem v řece, bylo nazváno Praha. Dnešní urbanisté se rovněž domnívají, že nejdůležitější a současně nejvíce charakteristické pro vznik Prahy byly právě říční brody, na rozdíl od říčních břehů či činností prováděných v okolí řeky.
Podle jiných vysvětlení bývá pojmenování spojováno také jednak s pražením (opracováním ohněm) ať už obilí, kovů nebo lesa, a jednak s vyprahlým návrším, ostrohem nad brodem, na kterém byl postaven Pražský hrad, tedy na takzvané prazje, což je označení pro sluncem vyprahlé místo či označení pro takovou půdu samotnou.
Pověst o založení Prahy název vysvětluje tím, že kněžna Libuše nechala založit město tam, kde osadník uprostřed lesa tesal práh ke svému srubu.
Na území dnešní Prahy sídlila v předhistorické době řada nejrůznějších kmenů – poslední nálezy u Křeslic datují zdejší osídlení do doby před sedmi tisíci lety (jde o kulturu s lineární – dříve volutovou – keramikou).
Okolo 200 let př. n. l. bylo na místě Závist založeno sídliště Keltů (Bojové). Kolem oblasti, kde nyní stojí Praha, zmiňuje Ptolemaiova mapa (2. století n.l.) germánské město s názvem „Casurgis“. Během stěhování národů v 6. století, začali osídlovat pražskou kotlinu Slované.
Podle legendy byla Praha založena v 8. století českou kněžnou a věštkyní Libuší a jejím manželem Přemyslem, zakladatelem dynastie Přemyslovců. Legenda říká, že Libuše vyšla na skalnatý útes vysoko nad Vltavou a prorokovala: „Město vidím veliké, jehož sláva hvězd se bude dotýkat.“ Na místě nařídila vystavět hrad a město nazvala Praha.