Harlem era una zona coneguda pels indígenes com Muscoota (plana) i que van utilitzar com a camp de cultiu gràcies a les seves fèrtils terres. En 1658, el governador holandès Peter Stuyvesant, aprofitant la riquesa del terreny, va fundar aquí un llogaret amb el nom de Nieuw Haarlem, en honor a la ciutat holandesa Haarlem. Amb la conquesta de l'illa pels anglesos, les famílies de l'alta societat establir a Harlem seves hisendes i van construir les seves cases de camp. començaments del segle XX, l'agent immobiliari afroamericà Philip Payton arrendar gran quantitat d'immobles devaluats, rellogats a membres de la seva mateixa comunitat negra que havien estat desallotjats d'altres parts de la ciutat. El 1920, a mesura que la comunitat blanca abandonava el barri, sorgia el famós renaixement de Harlem ("Harlem Renaissance") amb l'arribada d'artistes, músics i intel.lectuals negres vinguts de tot el país. L'alta societat afroamericana es va instal.lar al sector conegut com Sugar Hill, a l'oest de Harlem. La cultura afroamericana i sobretot la seva música es va posar de moda a tota la ciutat gràcies a clubs com el Cotton Club o l'Apollo Theatre en què actuaven músics de color per a un públic exclusivament blanc. En els anys 1960, el barri va ser radicalitzant apareixent ideòlegs revolucionaris com Malcom X que pretenia invertir el racisme cap a la raça blanca. Harlem va ser degenerant fins convertir-se en el mític barri perillós. Al llarg de tot Harlem i el veí sud del Bronx, els apartaments eren incendiats pels mateixos propietaris per cobrar l'assegurança i desallotjar els inquilins creant un ambient desolador. Però el barri de Harlem té molt més interès històric i cultural, a part de la tradició del gospel. Doncs, si bé des que en el que avui ocupa Harlem ja el 1658 es van instal.lar les primeres comunitats procedents d'Holanda, i en èpoques posteriors també van residir comunitats d'alemanys, italians, irlandesos i jueus, Harlem és actualment conegut a tot el món com un centre de la comunitat negra. Va ser a principis segle XX quan, davant d'un excés d'oferta de cases sense habitar, construïdes davant les expectatives creades per la construcció del ferrocarril subterrànies, al barri de Harlem es va promoure que aquestes cases foren ocupades per població de raça negra provinent del baix Manhattan , d'Amèrica del Sud i del Carib. Aquests passejos són guiats per residents al barri, i coneixedors de la seva història. Són diverses les opcions disponibles, amb una durada d'entre dos i tres hores, i un preu d'entre 25 i 40 dòlars per persona. Les temàtiques varien des de "Renaixement de Harlem", fins al "Teatre Apollo", incloent, per descomptat, "Gospel a Harlem".