Standing on the shores of the strait that separates Vardoya Island from Norway, the Steilneset is a brooding, complex structure. A regimented forest of wooden supports, it stalks across the rough rocky ground on the edge of the small town of Vardø. Designed by architect Peter Zumthor and artist and past Wallpaper* guest editor (W*115) Louise Bourgeois, the Steilneset is a memorial, a physical structure for the remembrance of the sins of an earlier, unforgiving and rather more brutal era.

In the dark days of the early 17th Century, the witch mania that infected almost all of Europe reached this small fishing community and tore it apart. Armed with accusations and confessions - the texts of which have survived the centuries intact - the accidents, illnesses, errors and complexities of a harsh rural existence were instead attributed to 91 unfortunates, all of whom were believed to have made a personal pact with the devil. Over the course of roughly 100 years, those accused of such witchcraft were either burnt at the stake or tortured to death.

To memorialise such a distant and culturally complex event is a tall order; even more so when the finished memorial needs to be a tourist attraction in its own right. Bourgeois and Zumthor were appointed as part of Norway's ongoing National Tourist Routes programme, an expansive and hugely ambitious scheme to criss-cross this vast nation with man-made viewpoints and destinations that enhance the already spectacular natural landscapes. There are 18 routes in all, the majority clustered around the steep valleys and Fjords to the south-west.

Svein Ronning, the art curator for the NTR project, invited Bourgeois to design the memorial, with Zumthor as her collaborator. The slow back and forth between the pair, living and working on different continents, eventually led to Zumthor kick-starting the design and creating two structures, one enclosure for the artwork itself and a long, abstract pavilion containing information about the dark events of the past.

When wallpaper* was last up in these chilly latitudes, back in late 2008, the seaweed-encrusted shores of the northerly were yet to be sullied by bulldozers and workboots (see W*115). Our correspondent walked the icy site with Peter Zumthor and everyone tried to imagine exactly how it would be once the Swiss architect's collaboration with the New York based artist was complete. The following 18 months saw budget increases, design complications and, sadly, the death of Bourgeois at the age of 98.

But now the memorial is finished, opened by Queen Sonja and firmly putting Vardø on the map. We recently made a return trip to the town, making sure to pack our most efficient base layer for the three flight journey to this easterly tip of Europe. Here, on the edge of the freezing expanses of the Barents Sea, the final few wires were being wound into place and the churned up ground beneath the buildings was being shovelled back into an approximation of untouched landscape.

Vardø is very self-contained. The town's fish processing industry is long gone, appropriated by Chinese suppliers and off-shore factory ships. The town sucks in plenty of government subsidy and the emphasis is on bringing in tourists - mostly birdwatchers - and stopping the residential exodus by betting big on a new gas field supply depot, the Vardø Barents Base, just along the coast to boost local employment.

The townscape is littered with abandoned houses, their primary coloured weatherboarding and thick net curtains concealing their lack of inhabitants. A local museum plays up the longstanding cultural and economic connection to Russia - the border post is just a few miles along the coast - neglecting to mention the former Soviet Union's proximity initiated another key spoke in the economy - the silvery blue dome of a US military radar installation - operated by the Norwegian military - still dominates the town.

From the distant hump of Domen Mountain, the ridge that overlooks the town (once believed to be a meeting place for the witches' Sabbath), Vardø reads as a series of abstract forms; the colourful scatter of its houses, the white spike of Vardø church, the Globus II radar, and the star-shaped fortifications of the Vardøhus, home to a modest museum as well as the island's only two trees and commanding officer Major Tor Arild Melby (who serves a mean smoked whalemeat canapé). The Steilneset joins this group, another object in a grand still life (an approach crystallised in Zumthor's elegant working models).

Zumthor's pavilion dominates the site, located just a few minutes walk from the town centre. Taking inspiration from the vast wooden racks once used to dry the daily catch, the structure strides for 125 metres along the rocky beach. The tall wooden frame contains a stretched, taut canvas object, light coloured on the outside but dark and murky within. This long corridor is accessed via a ramp, taking visitors up into the heart of the pavilion, their views and sense of the surroundings strictly mediated. The chief sources of light are 91 windows, one for each victim, each accompanied by a solitary bulb and a printed piece of silk that sets out the accusation, confession and fate of those brought before the court. It's a sombre space, kept barely above the brisk temperature on the shore outside, and smelling strongly of wood and wood treatment. Zumthor apparently chose the location of each window by throwing a dice, a method as arbitrary and cold as the 'trial by water' that sealed so many fates.

Alongside the information centre is a black glass cube housing Bourgeois's artwork, The Damned, The Possessed and The Beloved. Again, the structure is open to the elements, and the smoked glass plays with this northerly location's relentless summer daytime (and corresponding winter darkness). The five jets of fire in the flaming chair dance grotesquely in the seven mirrors above it, evoking the families that were literally torn apart by fire. Any misgivings one might have about the apparent simplicity of the statement are dismissed by the atmospheric qualities of the site.

The Varanger stretch of the National Tourist Routes might not have the visual drama of sheer-sided Fjords; it's a more contemplative, rugged and lonely landscape. The 154km route through Finnmark from Gornitak to Hamningberg is sparsely populated but magically lit, a rare place where the inherent strangeness of architectural interventions is enhanced to the point of being an almost spiritual experience. The sins of the past are presented baldly, their emotional impact still as strong now as it must have been over 300 years ago. Like so many of Peter Zumthor's other works, we suspect the Steilneset will become a place of pilgrimage. The visitors might have architectural motivations at first, but their journey can't fail to be touched by the geography and history of this magnificent landscape.