Harlemi tantsuteater sündis peamiselt Arthur Mitchelli, esimese Aafrika-Ameerika meestantsija, kes sai rahvusvaheliselt tuntud balletikompanii alaliseks liikmeks, jõupingutustel. Mitchell debüteeris New Yorgi balletis George Balanchine’i Lääne-sümfoonias 1955. aastal. Ta tantsis koos seltskonnaga 15 aastat. Kui ta kuulis dr Martin Luther Kingi noorema mõrvast, läks ta Harlemisse, et saaks kohalikele lastele tantsu õpetada.
Mitchell hakkas kohalikele Harlemi kooli lastele balletitunde andma 1968. aastal. Tunnid toimusid kiriku keldris. Esialgu andis ta tunde lahtise välisuksega, et möödujad saaksid õpilasi tööl jälgida. Ta alustas 30 õpilasega, kuid suve lõpuks oli koolis registreerunud 400 õpilast. 1969. aastaks sai Harlemi tantsuteatrist ametlikult kooli- ja balletikompanii.
1969. aastal tuuritasid üliõpilased peamiselt kohapeal, pakkudes loenguid-demonstratsioone. Varsti pärast seda oli Mitchell kokku pannud 20 professionaalsest tantsijast koosneva trupi, kes debüteeris 1971. aasta festivalil Itaalias Spoletos. Pärast kahte ringreisi Euroopas ja kolme riigisiseste ringreisi nautis vastsündinud ettevõte oma esimest ametlikku hooaega New Yorgis.
1981. aastal olid nad esimene mustanahaline balletikompanii, kes tantsis Londoni mainekas Covent Gardenis. Vaid aasta hiljem tantsisid nad New Yorgi Metropolitani ooperiteatris. Spetsialiseerudes George Balanchine’i, Jerome Robbinsi ja Arthur Mitchelli koreograafilistele ballettidele, on nad tuntud ka klassikaliste ballettide, nagu Giselle ja Luikede järv, esitamise poolest.
Märkimisväärsed tantsijad, kes on esinenud Harlemi tantsuteatris, on Virginia Johnson, Stephanie Baxter, Eddie Shellman, Mel Tomlinson, Alicia Graf ja Donald Williams. Nende jõupingutused aitasid Harlemi tantsuteatril saada teedrajavaks tantsukompaniiks. Nad tõestasid maailmale, et Aafrika-Ameerika tantsijad suudavad esitada klassikalist balletti sama suurepäraselt kui ükski teine seltskond kogu maailmas.
Harlemi kooli tantsuteater treenib tantsijaid seltskonna jaoks, kuid kutsub ka noori meelelahutuslikke tantsijaid selle käsitööd õppima. Tantsutunnid on kolmel tasemel: kogukondlik, eelprofessionaalne ja professionaalne. Tunde pakutakse erinevates stiilides, sealhulgas ballett, stepp, jazz, kaasaegne tants, Aafrika tants, iiri stepptants, võimlemine, karate ja isegi tai chi. Muusikateooria ja tantsuajalugu on teised olulised õpilastele pakutavad tunnid.
Harlemi tantsuteater viib läbi mitmeid teavitusprogramme, et harida kogukonda tantsust. Üks programm kannab nime Dancing Through Barriers. See pakub kohalikele koolidele ja kogukondadele mitmesuguseid tegevusi, töötubasid ja meeleavaldusi. Ettevõte soovib inspireerida igasuguse etnilise taustaga lapsi arendama armastust etenduskunstide vastu.
Pärast rahalisi raskusi sulges kool 2004. aastal ajutiselt uksed ning ettevõte koondas umbes 44 tantsijat. Õnneks avati kool kuus nädalat hiljem tänu murelike balletisõprade pingutustele kogu maailmas. Raha kogumine mitmesugustest üksikisikutest, valitsusasutustest, ettevõtetest ja sihtasutustest aitas ettevõtte ja kooli taaselustada.