Descendiente de una familia judía, desde niño muestra una precoz aptitud por la música, tal vez heredada de su madre Noemí Senigaglia. A los 10 años de edad compuso dos piezas musicales para piano que fueron publicadas en una revista juvenil. A un principio su padre se oponía a que Mario siga una carrera musical, pues, de acuerdo a las tradiciones familiares se esperaba que fuera un banquero.
Obstinadamente, el joven prosiguió sus estudios de piano en el conservatorio Cherubini de Florencia con M. Edgardo del Valle. También tuvo como maestros a Ildebrando Pizzetti. En el verano de 1924 conoce a Giacomo Puccini y entabló una estrecha relación con Arturo Toscanini que dirigió varias de sus obras. En un festival en Venecia, en 1932, conoce a Andrés Segovia y desde entonces Mario Castelnuovo-Tedesco empieza a componer para la guitarra.
Así comienza una estrecha relación con Segovia que duraría 36 años, la cual permite que Castelnuovo-Tedesco componga como 350 obras para guitarra. En 1939 toda su familia se traslada a Nueva York, y Mario obtiene finalmente la nacionalidad estadounidense en 1946, después de dedicarse en este lapso a componer música para películas para una firma norteamericana.
En 1958 fue reconocido por su obra «El Mercader de Venecia», que obtuvo el primer puesto en el concurso de Campari en el teatro de La Escala de Milán. Su obra es muy variada y van desde composiciones para coro, orquesta, instrumentos solos, obras orquestales y escénicas. Su contribución fundamental al repertorio de la guitarra son sus cuatro conciertos para guitarra y orquesta: Concierto en Re Op. 99, Serenade Op. 118, Segundo Concierto en Do Op. 160, Concierto Op. 201 para 2 guitarras y orquesta. De la Serenade Op. 118 solamente se encuentra disponible la versión reducida para guitarra y piano, pues la versión con orquesta no está publicada.
También se encuentra no editada otra obra para guitarra y orquesta: el Concierto Capriccio diabolico Op. 85b. Castelnuovo-Tedesco compuso varias obras para dúo de guitarra y voz o piano, y algunas transcripciones, muchas de las cuales no se encuentran publicadas.
Pretendió realizar un método didáctico para guitarra que quedó incompleto, a invitación de Ruggero Chiesa, y que se concretó parcialmente en sus «Quaderni, Preludi y Studi Op. 210». Segovia ya le había propuesto muchos años antes la realización del método.
La figura de Castelnuovo-Tedesco hoy en día es reconocida como la de un artista muy versátil, con un estilo muy diferente al de su maestro Pizzetti y de sus contemporáneos, muy peculiar por la ausencia de imitación.
Es evidente el amor que tenía hacia la literatura, la poesía y el teatro, como claro ejemplo se encuentra su Op. 190 «Platero y Yo» compuesto para voz y guitarra, que se basa en los 28 poemas del Nobel de literatura J.R. Jiménez o los 24 Caprichos de Goya op. 195 inspirados en los óleos de Francisco Goya y dedicados a su hijo Lorenzo, estudiante de arquitectura. Mario Castelnuovo-Tedesco muere en 1968.