Harlemo šokio teatras pirmiausia gimė Arthuro Mitchello, pirmojo afroamerikiečių šokėjo, nuolatiniu tarptautiniu mastu žinomos baleto grupės nariu, pastangomis. Mitchellas Niujorko balete debiutavo 1955 m. George’o Balanchine’o Vakarų simfonijoje. Su kompanija jis šoko 15 metų. Išgirdęs apie daktaro Martino Lutherio Kingo jaunesniojo nužudymą, jis nuvyko į Harlemą, kad galėtų mokyti vietinius vaikus šokio.
Mitchellas pradėjo vesti vietos Harlemo mokyklos vaikams baleto pamokas 1968 m. Pamokos vyko bažnyčios rūsyje. Iš pradžių pamokas vedė atviromis durimis, kad pro šalį einantys žmonės galėtų stebėti besidarbuojančius mokinius. Jis pradėjo nuo 30 mokinių, tačiau vasaros pabaigoje mokykloje užsiregistravo 400 mokinių. Iki 1969 m. Harlemo šokio teatras oficialiai tapo mokyklos ir baleto trupe.
1969 m. studentai daugiausia gastroliavo vietoje, skaitė paskaitas-demonstracijas. Neilgai trukus Mitchellas subūrė 20 profesionalių šokėjų trupę, kuri debiutavo 1971 m. festivalyje Spolete, Italijoje. Po dviejų turų po Europą ir trijų nacionalinių turų jauna kompanija mėgavosi savo pirmuoju oficialiu sezonu Niujorke.
1981 metais jie buvo pirmoji juodaodžių baleto trupė, šokusi prestižiniame Londono Kovent Gardene. Vos po metų jie šoko Metropoliteno operos teatre Niujorke. Specializuojasi George’o Balanchine’o, Jerome’o Robbinso ir Arthuro Mitchello choreografiniuose baletuose, jie taip pat yra gerai žinomi dėl klasikinių baletų, tokių kaip „Žizel“ ir „Gulbių ežeras“, atlikimo.
Žymūs šokėjai, koncertavę Harlemo šokio teatre, yra Virginia Johnson, Stephanie Baxter, Eddie Shellman, Melas Tomlinsonas, Alicia Graf ir Donaldas Williamsas. Jų pastangos padėjo Harlemo šokio teatrui tapti novatoriška šokių kompanija. Jie pasauliui įrodė, kad afroamerikiečių šokėjai gali atlikti klasikinį baletą taip pat puikiai, kaip ir bet kuri kita kompanija visame pasaulyje.
Harlemo mokyklos šokio teatras rengia šokėjus kompanijai, bet taip pat kviečia jaunuosius laisvalaikio šokėjus mokytis šio amato. Yra trijų lygių šokių pamokos: bendruomeninis, ikiprofesionalus ir profesionalus. Siūlomi įvairių stilių užsiėmimai, įskaitant baletą, stepą, džiazą, šiuolaikinius, afrikietiškus šokius, airiškus žingsnius, gimnastiką, karatė ir net tai chi. Muzikos teorija ir šokio istorija yra kitos svarbios studentams skirtos pamokos.
Harlemo šokio teatras vykdo kelias informavimo programas, skirtas šviesti bendruomenę apie šokį. Viena programa vadinasi Dancing Through Barriers. Vietos mokykloms ir bendruomenėms ji siūlo įvairią veiklą, seminarus ir demonstracijas. Bendrovė nori įkvėpti visų etninių grupių vaikus, kad jie ugdytų meilę scenos menui.
Patyrusi finansinių sunkumų, 2004 metais mokykla laikinai uždarė duris, bendrovė atleido apie 44 šokėjus. Laimei, susirūpinusių baleto mylėtojų visame pasaulyje pastangomis mokykla vėl atidaryta po šešių savaičių. Lėšų rinkimas iš įvairių privačių, vyriausybinių, įmonių ir fondų šaltinių padėjo atgaivinti įmonę ir mokyklą.