Si trasferisce in America per studiare regia alla New York University dove si laurea nel 1995. Dopo aver girato diversi corti, esordisce nel lungometraggio nel 1997 con Once We Were Strangers, prodotto con i soldi ricavati dalla vendita di un paio di orecchini ricevuti in eredità dalla bisnonna. Con questo primo film, in cui racconta l'amicizia di due immigrati, un italiano e un indiano, che vivono a New York arrangiandosi tra mille lavoretti, Crialese partecipa al Sundance film festival di Robert Redford. Nel 2002 vince la settimana della critica a Cannes con Respiro, che dopo aver entusiasmato la Francia ottiene un notevole successo anche in Italia. Interpretato da una bravissima Valeria Golino e ambientato in una Lampedusa aspra e solare, Respiro sembra unire la lezione del neorealismo italiano con slanci onirici che si rifanno a Vigo (di cui si cita la sequenza "sommersa" de L'Atalante) senza presunzione, con sincerità e coraggio senza paura di confondere la realtà con il mito.