Built in 1873-1874, the former Magazine was part of the Armed Constabulary redoubt at Tapuaeharuru, later known as Taupo. The redoubt was established in early 1870 on high ground overlooking an important crossing of the Waikato River, about 180 m. below the river's outflow from Lake Taupo. The fortification lay at the northern end of a chain of Armed Constabulary posts that protected the 87 km. route between Taupo and Napier. Tapuaeharuru was of great strategic value as it controlled the convergence of Maori bridle tracks linking the Waikato and the Ureweras to the north and south, and Tauranga and Wanganui to the east and west. Control of this communications network became particularly important for the colonial government during its campaigns against Te Kooti Arikirangi Te Turuki (?-1893), particularly after Te Kooti extended his operations from the Ureweras in 1869. The government feared an escalation of the revolt that might also encompass the Kingite movement of King Potatau in the King Country.

Located in the traditional territory of Ngati Tuwharetoa, the redoubt was established on the opposite side of the Waikato River to Tapuaeharuru pa, as well as Te Poihipi Tukairangi's settlement at nearby Nukuhau. Its establishment reinforced the support of local Maori leaders such as Te Poihipi, whose pa was reported in the mid 1860s as being one of only two around the lake not to support the Kingite movement. The Armed Constabulary force at Taupo was first based in Te Poihipi's pa, but was required to move to a purpose-built redoubt after a drunken constable set fire to a house, nearly engulfing the settlement. Created in 1867 to supplement British Imperial troops in government campaigns, the Armed Constabulary was made up mostly of single men of European birth, and primarily undertook garrison duties, construction projects and the maintenance of civil order.

The new fortification at Tapuaeharuru was designed to take 150 men in tents although its occupants generally numbered between 15 and 40 during the early 1870s. A number of buildings were erected both inside and outside its earth and pumice defences, including quarters for officers and men, mess rooms, stores, stables and other ancillary buildings. The surrounding area incorporated a vegetable garden and paddock, while a firing range was also established. Two boat houses were constructed beside the river to contain the whaleboats that the constabulary used to ferry men and supplies around the lake.

The magazine was erected inside the fortification by the middle of 1874 to house munitions used by the Tapuaeharuru force. The redoubt's occupants were armed, having been issued with medium-converted Snider rifles in November 1870, replacing the less accurate Enfield and Short Snider guns. Rifle practice formed an important part of the constabulary's drill, with an annual course in musketry and competitions such as the Colonial Prize Firing tournament. The rifle range at Tapuaeharuru was also levelled and improved in the same year that the magazine was built.

As a valuable and potentially dangerous commodity, the munitions required storage in a building that was both secure and visible. The magazine was positioned towards the rear, or western wall of the redoubt, facing the main entrance in the eastern line of defences. Needing to be fireproof it was also constructed of pumice stone, unlike most of the other buildings in and around the redoubt, which were made of timber or raupo.

The pumice is said to have been quarried at Aratiatia, some distance downstream along the Waikato River. Wood for the internal lining and roof frame of the structure was probably brought in from Opepe, along with most other timber building material at this time. The stonework was constructed by an unknown member of the Armed Constabulary force in the Taupo district, who was described in 1874 as having been kept 'constantly employed at his trade as a mason in the erection of chimneys (pumice), and magazines of the same material, at the various stations'. A slightly larger magazine was erected in the same year at Opepe - the headquarters of the Armed Constabulary in the Taupo district until 1877, when this function moved to Tapuaeharuru. The Opepe magazine was similarly built of pumice, but was further noted as being 'roofed with cement'.

The Tapuaeharuru magazine was presumably used until January 1885, when the Armed Constabulary was withdrawn from the redoubt. The constabulary was formally disbanded the following year in favour of a civil police force. While many of the buildings within the redoubt are assumed to have fallen into disrepair or have been removed, some evidently continued in use. A structure believed to have been the officers' mess was used as the Taupo Post and Telegraph Office in the late nineteenth century, before being occupied as a dwelling by a telegraph lineman in the early 1900s. The former Magazine may have functioned as an outbuilding associated with this or another building on the site until the middle of the century.

In 1940, the redoubt was incorporated into Taupo Domain at the request of the Town Board, while the former Post and Telegraph Office was moved and partly incorporated into the Town Board offices in Story Place in 1947. Renewed interest in the historic nature of the site in the 1960s led to the magazine being restored. Work included the replacement of most of the building's timber interior, which was assembled off-site and lifted into the magazine after the roof had been removed. Some of the stonework was also re-set using Portland cement. Having been set aside as a historic reserve in 1968, the redoubt and magazine were formally managed by Heritage New Zealand (formerly New Zealand Historic Places Trust) until March 2019, when the property was transferred to Tuwharetoa as part of the Treaty settlement.