Родился во Флоренции, был третьим ребёнком в семье Амадео Кастельнуово-Тедеско (1859—1947) и Ноэми Кастельнуово-Тедеско (урождённой Сенигалья, 1872—1940). Отец, сефардского происхождения, был занят в банковском деле; мать происходила из семьи римских евреев. Семья Кастельнуово-Тедеско была религиозной и занимала видное место в еврейской общине Флоренции. У Марио были старшие братья Уго (1890—1974), впоследствии поэт, и Гвидо (1891—1960).
Учился игре на фортепиано (сперва частным образом, затем во Флорентийской консерватории) у своего дальнего родственника по матери Эдгардо дель Валле-де-Паса, оказавшего на него большое влияние. Затем изучал композицию под руководством Ильдебрандо Пиццетти.
С принятием расовых законов в Италии в 1939 году эмигрировал с женой в США. С 1946 преподавал композицию в консерватории в Лос-Анджелесе. Творчество Кастельнуово-Тедеско во многом связано с тосканской музыкальной культурой. Его произведения пользовались успехом в 1920—1930-х годы. Среди его сочинений — оперы, произведения для хора, ансамблей, камерные сочинения, концерты для скрипки, виолончели, арфы и фортепиано с оркестром, а также музыка более, чем к двумстам кинофильмам и др.
Один из наиболее выдающихся гитарных композиторов XX века. Им создано более ста оригинальных произведений для классической гитары. В том числе, несколько концертов для гитары и симфонического оркестра.
Двоюродная сестра — переводчица Лина Кастельнуово, которой посвящёна «Мемориальная литургическая служба» композитора (1960). Написал ещё несколько произведений на основе иудейской литургии.
