W Paryżu, Cavaillé-Coll został przedstawiony Henri Montan Bertonowi, członkowi komisji powołanej w sprawie budowy organów w bazylice św. Dionizego w Saint-Denis. Po zapoznaniu się z wnętrzem świątyni, w zaledwie 3 dni naszkicował projekt organów. Ku zaskoczeniu wszystkich, młody i jeszcze nieznany Aristide, otrzymał kontrakt 2 października 1834 roku, wygrywając z innymi renomowanymi we Francji organmistrzami. Po otrzymaniu tej wiadomości, jego ojciec również przeniósł się do Paryża, gdzie wraz ze swoim synem otworzył warsztat organmistrzowski w pobliżu kościoła Notre-Dame-de-Lorette.
Zgodnie z umową z 1833 roku, organy w Saint-Denis miały zostać zbudowane w ciągu trzech lat za cenę 80 000 franków i miały posiadać 81 głosów na pięciu manuałach. Rok później, prawdopodobnie pod naciskiem ojca, cenę podniesiono do 85 000 franków, a liczbę głosów. zmniejszono do 71. Wydawało się, że harmonogramu nie uda się dotrzymać, ale szczęśliwie dla Cavaillé-Colla, prace budowlane we wnętrzu kościoła opóźniły się.