A los 20 años, se convirtió en la persona más joven en recibir el Premio a la Mejor Actriz de su país para su papel protagónico en War and Youth, la película última película del renombrado Director Tadeshi Imai. Este papel también le hizo ganar el Premio a la Mejor Actriz de los Críticos de Cine de Japón, en el Festival de Cine de Hochi y la 34? Premio de la Cinta Azul.
La fase americana de la carrera de Kudoh fue impulsada por Jim Jarmusch, que la seleccionó para la película Mystery Train como parte de una pareja de amantes del rock en peregrinaje a Memphis. Esta temprana le valió a Kudoh una nominación al Premio como Mejor Actriz en el Independent Spirit Awards.
Cantante así como actriz bilingüe, Kudoh es algo así como un icono para las mujeres jóvenes en su nativo Japón. Su carrera comenzó cuando tenía solamente 12 años, al ser descubierta en las calles de Tokio por un agente. Aunque el mundo del espectáculo no le era del todo desconocido (su madre es una famosa cantante), Kudoh debutó posteriormente en una comedia alocada, The Crazy Family que fue mostrada en el Festival de Cine de Cannes y se convirtió en una película de culto en Japón. Ella cantó varias canciones en la película, algo que sirvió para lanzar su carrera en la música. Ha grabado siete álbumes y se ha convertido en una estrella de la música pop alternativa en Japón.