Учился сперва в Берлине, затем в Лейпцигской консерватории у Феликса Мендельсона и Роберта Шумана и наконец в Вене у Симона Зехтера. С 1846 г. преподавал в Венской консерватории. В 1862 г. Ноттебом познакомился с Иоганнесом Брамсом, став одним из его близких друзей; Брамс ухаживал за Ноттебомом во время его последней болезни, был устроителем его похорон и унаследовал собранную Ноттебомом коллекцию барочной и добарочной вокальной и инструментальной музыки.
Музыковедческие труды Ноттебома были посвящены, прежде всего, Бетховену, начиная с книги «Очерки о Бетховене» (фр. Etudes de Beethoven; Лейпциг, 1865). Наибольшее значение имеет работа Ноттебома над записными книжками, в которых Бетховен набрасывал черновики своих произведений; последние сочинения Ноттебома в этой области были опубликованы посмертно его учеником Ойзебиусом Мандычевским. Он составил также тематические указатели опубликованных произведений Бетховена (фр. Catalogue th?matique des oeuvres publi?es de Ludwig van Beethoven, avec des observations chronologiques et bibliographiques; 1868) и Шуберта (фр. Catalogue th?matique des oeuvres publi? es de Franz Schubert; 1875).
Композиторское наследие Ноттебома невелико и состоит, главным образом, из фортепианной и камерной музыки. Определённой известностью пользовались его Вариации на тему сарабанды Баха для двух фортепиано (op. 17), которые Ноттебом часто исполнял дуэтом с Брамсом.
Среди учеников Ноттебома, в частности, Август Страдал и Эдуард Вахман.