It was built for the 369th Regiment, also known as the "Harlem Hellfighters", founded in 1913 as the first National Guard unit in New York State composed solely of African-Americans.

The administration building, built in the Art Deco style between 1930 and 1933, was designed by John S. Van Wart and Sidney Wein.

The attached medieval-inspired drill shed, built between 1921 and 1924, was designed by Tachau and Vought and measures 50,000 square feet (4,600 m2).

[2] After the American Civil War ended, the New York state government passed a law, which mandated that armories be erected for volunteer regiments by each of the individual counties.

[2] By the late 19th and early 20th century, the former Dutch colonial settlement of Harlem was being developed into a primarily African-American neighborhood, having become accessible via the newly built New York City Subway.

[8][10] The 15th Regiment, whose parent unit was constituted in the New York Army National Guard in 1913, was officially organized three years later, in preparation for being deployed to France during World War I.

The 15th was the first National Guard regiment constituted based on race, as it was composed primarily of African Americans, but also included servicemembers from Puerto Rico, the West Indies, Canada, and several countries in Europe and Africa.

[11][8][12] The regiment reached its full strength of 2,000 men by 1917, and trained in New York and South Carolina because they did not yet have their own armory.

[14][15] The 369th Regiment (also known by their nickname, the "Harlem Hell Fighters") was initially housed at Astor Row on West 130th Street.

The new building would include a shooting range, auditorium, mess hall, and rooftop tennis courts.

[25] Twelve firms submitted designs for the drill shed,[26] and the commission was ultimately given to the lowest bidder, John S. Van Wart and Sidney Wein.

[19] However, the New York Daily News reported in January 1934 that the 369th Regiment had refused to accept title to the administration building, citing various work defects such as a leaky roof.

[30] The 369th Regiment Armory also hosted sporting events, such as track and field competitions[31] and tennis matches.

[42] The Police Athletic League of New York City used part of the 369th Regiment Armory's drill shed as a community center starting in 2006.

[44] In September 2012, a community program painted a mural on the armory's walls that was devoted to the 369th Regiment's history.

[43][49] Despite fears that children at the armory may have been susceptible to lead poisoning for over a decade, state officials said that the cleanup was limited to the basement, which was off-limits to kids.

[51] The armory is composed of two structures in contrasting architectural styles: the medieval-style drill shed and the Art Deco-style administration building.

[11][52] The surrounding areas are composed of industrial buildings, while the Harlem River Drive runs on the opposite side of Fifth Avenue across from the armory.

[53] The 3+1⁄2-story, rectangular administration building features a terracotta parapet embellished with chevron designs and stylized eagles.