The Flushing Armory was designed and constructed between 1904 and 1905. The Armory was to house the 17th Separate Company, which was founded in 1876. Before relocating to the Flushing Armory, the Company had headquarters between Lawrence Street and Northern Boulevard. After World War I, the 17th became Company I, which was part of Brooklyn's 14th Regiment. The building was abandoned by the military in the 1990s. After the military left the Flushing Armory, the building became a shelter for homeless women. It was later turned into a gymnasium until the NYPD's Queens North Taskforce moved into it. The building is currently occupied by the Taskforce.
When the Flushing Armory was designed, it was the first armory built in New York City during the 20th Century. However, Heins had designed similar armories elsewhere, including the Sixth Battery in Binghamton, the Third Separate Company in Oneonta, and the 19th Separate Company in Gloversville. Heins goal was to create a castle-like building that resembled those found across Europe. The building was constructed with brick and stone. To give it a towering presence, a five-story tower was added onto the corner of the building and a large entrance pavilion was included on the front. Thanks to its historical importance, the Flushing Armory was added to the National Register of Historic Places in 1995.