Dance Theater of Harlem se je rodil predvsem s prizadevanji Arthurja Mitchella, prvega afroameriškega plesalca, ki je postal stalni član mednarodno priznane baletne skupine. Mitchell je leta 1955 debitiral v newyorškem baletu v Western Symphony Georgea Balanchina. Z družbo je plesal 15 let. Ko je slišal za atentat na dr. Martina Lutherja Kinga, mlajšega, je odšel v Harlem, da bi lahko lokalne otroke poučeval o plesu.
Mitchell je začel poučevati balet lokalnim šolarjem iz Harlema leta 1968. Pouk je potekal v kleti cerkve. Sprva je poučeval z odprtimi vhodnimi vrati, da so lahko mimoidoči opazovali študente pri delu. Začel je s 30 vpisanimi dijaki, do konca poletja pa je imela šola vpisanih 400 učencev. Do leta 1969 je Dance Theatre of Harlem uradno postal šolska in baletna družba.
Leta 1969 so študenti večinoma gostovali v kraju, kjer so izvajali predavanja-demonstracije. Kmalu zatem je Mitchell zbral skupino 20 profesionalnih plesalcev, ki so debitirali na festivalu leta 1971 v Spoletu v Italiji. Po dveh turnejah po Evropi in treh nacionalnih turnejah je novonastala družba uživala v svoji prvi uradni sezoni v New Yorku.
Leta 1981 so bili prva temnopolta baletna družba, ki je zaplesala v prestižnem londonskem Covent Gardenu. Le eno leto pozneje sta plesala v Metropolitan Opera House v New Yorku. Specializirani so za balete v koreografiji Georgea Balanchina, Jeromea Robbinsa in Arthurja Mitchella, znani pa so tudi po izvajanju klasičnih baletov, kot sta Giselle in Labodje jezero.
Pomembni plesalci, ki so nastopali s Dance Theater of Harlem, so Virginia Johnson, Stephanie Baxter, Eddie Shellman, Mel Tomlinson, Alicia Graf in Donald Williams. Njihova prizadevanja so pripomogla, da je Dance Theatre of Harlem postala pionirska plesna družba. Svetu so dokazali, da lahko afroameriški plesalci izvajajo klasični balet enako briljantno kot katera koli druga družba po svetu.
Plesno gledališče šole Harlem pripravlja plesalce za družbo, a tudi vabi rekreativne mlade plesalce, da se naučijo njegove obrti. Obstajajo tri stopnje plesnih tečajev: skupnostna, predprofesionalna in profesionalna. Tečaji so na voljo v različnih stilih, vključno z baletom, stepom, jazzom, modernim, afriškim plesom, irskim step plesom, gimnastiko, karatejem in celo tai chijem. Teorija glasbe in zgodovina plesa sta druga pomembna predavanja za študente.
Dance Theatre of Harlem izvaja več informativnih programov za izobraževanje skupnosti o plesu. En program se imenuje Dancing Through Barriers. Lokalnim šolam in skupnostim ponuja različne dejavnosti, delavnice in predstavitve. Podjetje želi navdušiti otroke vseh etničnih okolij, da razvijejo ljubezen do uprizoritvenih umetnosti.
Po finančnih težavah je šola leta 2004 začasno zaprla svoja vrata, družba pa je odpustila približno 44 plesalcev. Na srečo se je šola ponovno odprla šest tednov pozneje, zahvaljujoč prizadevanjem zaskrbljenih ljubiteljev baleta po vsem svetu. Zbiranje sredstev iz različnih virov posameznikov, vlade, podjetij in fundacije je pomagalo oživiti podjetje in šolo.