Území Újezda nad Lesy bylo osídleno již od 2. poloviny 3. tisíciletí př. n. l. Svědčí o tom archeologické nálezy při stavební činnosti v obci (keramika, kamenné nástroje, popelnice, kostrový hrob a další). Podle církevních pramenů tvořilo ves ve středověku asi 15 usedlostí ležících podél Staroújezdské ulice, což je jižní část dnešní obce směrem ke Kolodějům. Centrem byl kostel svatého Bartoloměje, jehož existence je doložena z roku 1309. Zvon z roku 1486 je dnes v kolodějském kostele Povýšení sv. kříže.

Dnešní obec Újezd nad Lesy, která je městskou částí hl. města Prahy, není celistvou osadou v historickém slova smyslu. Vznikla v roce 1921 sloučením Nové Sibřiny a Újezda s osadou Blatov. 7. února 1922 schválilo ministerstvo vnitra název nové obce Újezd nad Lesy.

První zmínky o osadě Blatov jsou z roku 1229. Původními osadníky Blatova byli dřevorubci, pracující v lese Fidrholci. Na některých prastarých německých a ruských mapách je osada Blatov vyznačena, přestože ves Újezd chybí. Prvním známým majitelem Újezda byl pan Vítek ze Švábenic, neboli Heřmanic, kterému patřila i ves Sibřina. 29. července 1309 prodává Újezd Klášteru na Zderaze. Roku 1395 kupuje Újezd pražská rodina bohatých měšťanů Rotlevů. Po bitvě na Bílé hoře připadl celý zdejší kraj v roce 1623 jako konfiskát knížeti Karlovi z Lichtensteina včetně Oujezda s poplužním dvorem "Na Fidrholci". Roku 1645 byla ves Oujedz vypálena a vypleněna Švédy. Zůstala pustá a neobydlená až do roku 1783, kdy kníže z Lichtensteina zde dal postavit 10 dřevěných domů, do nichž usadil německé rodiny. Někteří z obce odešli, někteří postupně splynuli s českým obyvatelstvem. Počet obyvatel se výrazně zvýšil v období tzv. "pražské kolonizace" v letech 1890-1914.

Dnešní Újezd nad Lesy je architektonicky nejednotnou zástavbou především podél státní silnice Praha - Kolín a podél staré silnice Koloděje - Šestajovice. Dodnes je zástavbou patrná i někdejší samostatnost osady Blatov.

Křižovatka silnic Praha - Kolín a Koloděje - Šestajovice se stala přirozeným centrem v novodobé historii obce. Vžil se zde i místní název "Na křižovatce", který se používá i dnes. Zde byl také od 1. světové války soustředěn společenský život. Bývalá Nová Sibřina měla své centrum kolem hospody "U Strassmajrů" (nyní "U Rohožníku"). V osídlení Blatova je vidět snaha po vytvoření návse, z níž dnes zbyla jen kaplička a křížek.

Téměř polovina katastru obce je pokryta lesním porostem, jehož biologická hodnota pro tvorbu životního prostředí je nesmírně důležitá.