Hārlemas dejas teātris radās galvenokārt Artūra Mičela, pirmā afroamerikāņu vīriešu dejotāja, centieniem kļūt par pastāvīgu starptautiski atzītas baleta grupas dalībnieku. Mičels Ņujorkas baletā debitēja 1955. gadā Džordža Balančina Rietumu simfonijā. Viņš dejoja kopā ar kompāniju 15 gadus. Uzzinājis par doktora Mārtina Lutera Kinga, jaunākā, slepkavību, viņš devās uz Hārlemu, lai varētu mācīt vietējiem bērniem dejas.
Mičels sāka sniegt vietējās Hārlemas skolas bērniem baleta nodarbības 1968. gadā. Nodarbības notika baznīcas pagrabā. Sākotnēji viņš pasniedza nodarbības ar atvērtām ārdurvīm, lai garāmejošie varētu vērot skolēnus darbā. Viņš sāka ar 30 uzņemtiem skolēniem, bet līdz vasaras beigām skolā bija reģistrējušies 400 skolēnu. Līdz 1969. gadam Hārlemas dejas teātris oficiāli kļuva par skolu un baleta uzņēmumu.
1969. gadā studenti pārsvarā apceļoja vietējās ekskursijas, sniedzot lekcijas-demonstrējumus. Neilgi pēc tam Mičels bija izveidojis 20 profesionālu dejotāju trupu, kas debitēja 1971. gada festivālā Spoleto, Itālijā. Pēc divām tūrēm pa Eiropu un trim nacionālajām tūrēm jaunizveidotā kompānija izbaudīja savu pirmo oficiālo sezonu Ņujorkā.
1981. gadā viņi bija pirmā melnādainā baleta grupa, kas dejoja prestižajā Koventgārdenā Londonā. Tikai gadu vēlāk viņi dejoja Metropolitēna operā Ņujorkā. Viņi specializējas Džordža Balančina, Džeroma Robbinsa un Artūra Mičela horeogrāfos baletos, un viņi ir arī labi pazīstami ar tādu klasisko baletu kā Žizele un Gulbju ezers atskaņošanu.
Ievērojami dejotāji, kas uzstājušies Hārlemas dejas teātrī, ir Virdžīnija Džonsone, Stefānija Bakstere, Edijs Šelmens, Mels Tomlinsons, Alisija Grāfa un Donalds Viljamss. Viņu pūles palīdzēja Hārlemas deju teātrim kļūt par novatorisku deju kompāniju. Viņi pierādīja pasaulei, ka afroamerikāņu dejotāji spēj izpildīt klasisko baletu tikpat izcili kā jebkura cita kompānija visā pasaulē.
Hārlemas skolas deju teātris sagatavo dejotājus uzņēmumam, kā arī aicina jaunos dejotājus apgūt savu amatu. Ir trīs deju nodarbību līmeņi: kopienas, pirmsprofesionālās un profesionālās. Nodarbības tiek piedāvātas dažādos stilos, tostarp balets, steps, džezs, modernās, afrikāņu dejas, īru stepa dejas, vingrošana, karatē un pat tai chi. Mūzikas teorija un dejas vēsture ir citas svarīgas nodarbības, kas tiek piedāvātas studentiem.
Hārlemas deju teātris vada vairākas informatīvās programmas, lai izglītotu sabiedrību par deju. Viena no programmām saucas Dancing Through Barriers. Tas nodrošina dažādas aktivitātes, darbnīcas un demonstrācijas vietējām skolām un kopienām. Uzņēmums vēlas iedvesmot dažādu etnisko piederību bērnus attīstīt mīlestību pret skatuves mākslu.
Pēc finansiālām grūtībām skola 2004. gadā uz laiku slēdza durvis, un uzņēmums atlaida aptuveni 44 dejotājus. Par laimi, skola atkal tika atvērta sešas nedēļas vēlāk, pateicoties norūpējušo baleta mīļotāju pūlēm visā pasaulē. Līdzekļu vākšana no dažādiem privātpersonu, valsts, korporatīvo un fondu avotiem palīdzēja atdzīvināt uzņēmumu un skolu.