Az első világháború idején katonai szolgálatot teljesített, a huszárhadnagyságig vitte. Ezután a budapesti egyetemen vegyészetet tanult, de művészi érdeklődése az Operaházba vitte, ahol díszletmunkásként dolgozott. 1919-ben a Tanácsköztársaság filmszcenikai ügyeit intézte, majd az Orient Film szcenikai főnöke lett. 1920-ban már a Mobil Filmvállalat forgatókönyvírója, főrendezője. Mikófalván népi passiójátékkal, majd az Egri csillagok megfilmesítésével próbálkozott, de pénzügyi nehézségek miatt kudarcba fulladt a forgatás, ő pedig 1923-ban elhagyta Magyarországot. Bécsben Max Reinhardt, Berlinben Fritz Lang mellett mint asszisztens leste el a filmszakma mesterfogásait.
1926-ban kivándorolt Amerikába, ahol a Rockefeller vegyészeti intézetben vegyésztechnikusként dolgozott, és közben orvos-bakteriolgógus képesítést szerzett. Sorsa újabb váratlan fordulatot vett: a Theatre Gould segédrendezője és dramaturgja lett, majd megtakarított pénzét is befektetve Hollywoodban 1928-ban leforgatta Az utolsó pillanat című filmet. A különös hangulatú dráma osztatlan sikert aratott, még Chaplin is lelkesen üdvözölte, s a kritikusok az év legjobb filmjének értékelték (a listán épp Chaplin Cirkusz című filmjét előzte meg).
Jelenet a Sonnenstrahl c. filmből
Fejőst az Universal filmgyár szerződtette, s újabb alkotása, A nagyváros mostohái szintén kivívta a szakmai közvélemény elismerését. Első hangosfilmje, az 1929-ben forgatott Broadway nagy sikert aratott, akárcsak A nagy ház című műve, majd az Emberek a rács mögött (Szerelmes ördög) című börtöndrámája.
Ekkor már világszerte a legnagyobb rendezőkkel emlegették egy sorban. 1932-ben rövid időre hazalátogatott, és francia tőkével két jelentős filmet forgatott: a Tavaszi záport és az Ítél a Balatont. Utóbbi - egy falusi Rómeó és Júlia története - kópiája elveszett, pedig olyan kitűnő színészek játszottak benne, mint Csortos Gyula, Páger Antal. Fejős Pál 1933-ban már Bécsben forgatott, nagy költségvetéssel készítette a Mégis szép az élet (Sonnenstrahl), majd a Tavaszi hangok (Frühlingsstimment) című filmjeit. A következő években Dániában élt és rendezett.
1935-36-ban a Svenk Film Industri megbízásából Madagaszkáron a szigetország törzseinek életét, szokásait, művészetét rögzítette celluloidszalagra, ezután egy svéd etnológiai expedíció tagjaként Indiában és Thaiföldön néprajzi filmeket készített. 1938 táján a régészet és az antropológia kedvéért végleg felhagyott a filmezéssel. Utolsó befejezett filmje a Sziámban forgatott Egy marék rizs, mely egy fiatal pár megélhetésért folytatott élethalálharcát mutatja be megrázóan. Expedíciójával a déltengeri Csütörtök-szigetek világát tanulmányozta, majd Latin-Amerika inka városaiban régészeti tanulmányokat folytatott.
A Fantomas plakátja
1941-től az amerikai Wenner-Gren antropológiai tudományos alapítvány igazgatója, 1955-től elnöke volt az 1963. április 25-én bekövetkezett haláláig. 1943-tól a Stanford Egyetemen, 1949-1951-ben a Yale Egyetemen, ezután 1955-ig a Columbia Egyetemen tanított kulturális antropológiát. A New York-i akadémia tagjaként nemzetközi szaktekintélynek számított, számos tudományos publikációja jelent meg. Halála után Farkas Ferenc zeneszerző, Fejős egyik legjobb barátja és számos filmjének komponistája Gyász és vigasz címmel zenekari művet írt emlékére.
Noha csak életének első felében filmezett Fejős Pál, a némafilmkorszak végén s az első hangosfilmek idején kifejtett munkásságával így is a világ legjobb filmalkotóinak sorába emelkedett.
