1897. január 24-én született Budapesten, apja gyógyszerész volt. Az első világháború idején katonai szolgálatot teljesített, és a huszárhadnagyságig jutott. Ezután Budapesten 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 idején az államosított filmgyártás ü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 a forgatás pénzügyi nehézségek miatt kudarcba fulladt, ő pedig 1923-ban elhagyta Magyarországot.
Bécsben Max Reinhardt, Berlinben Fritz Lang asszisztenseként leste el a filmszakma mesterfogásait. 1926-ban kivándorolt Amerikába, ahol a Rockefeller vegyészeti intézetben vegyésztechnikusként dolgozott, orvos-bakteriológus képesítést szerzett.
Sorsa újabb váratlan fordulatot vett: színházi segédrendező, később dramaturg 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). 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 is. Ekkor már világszerte a legnagyobb rendezőkkel emlegették egy sorban, de rá kellett döbbennie: Hollywood túl nagy árat kér a hírnévért, a művészi szabadság feladását.
1932-ben rövid időre hazalátogatott, francia tőkével két jelentős filmet készített Tavaszi zápor és Ítél a Balaton címmel. Az utóbbi egy falusi Rómeó és Júlia-történet, amely a magyar mellett angol, francia és német változatban is elkészült. Egyedül a német kópia maradt meg, a magyar változat megsemmisülése azért is nagy veszteség, mert olyan kitűnő színészek játszottak benne, mint Csortos Gyula és Páger Antal. Fejős Pál 1933-ban Bécsben forgatott, nagy költségvetéssel készítette a Mégis szép az élet (Sonnenstrahl), majd a Tavaszi hangok (Frühlingsstimmen) című filmjeit. A következő években Dániában élt és rendezett. 1935-36-ban a svéd 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.
