A wooden church has stood on this site since the 1660s, after Luleå's original settlement at Gammelstad was relocated to higher ground more suitable for trade. Later stone churches followed, but the previous building, Gustafskyrkan, was destroyed in the great town fire of 1887. The present cathedral was built to replace it, though construction ran over both schedule and budget after the original contractor failed to deliver; the parish itself eventually took over as builder. The church was consecrated in December 1893 and originally named Oscar Fredriks kyrka, after King Oscar II.
The building only became a cathedral in 1904, when Luleå stift was created by dividing the diocese of Härnösand, and the church was renamed accordingly. Built in red brick imported from Skåne, it is 54 metres long, 35 metres wide, and can seat around 500–520 people, with standing room for considerably more. Its tower rises to somewhere around 60–67 metres, sources giving slightly different figures.
The interior originally featured elaborate dark wood carving, wall paintings and decorated ceilings, but a 1936–38 renovation under architect Knut Nordenskjöld simplified and lightened the space considerably, removing much of the original decoration and painting the interior white. Some traces of the earlier, richer interior can still be seen in the church's entrance areas.
The cathedral's large gallery organ, built by the Gammelstad firm Grönlunds Orgelbyggeri and inaugurated in 1987, is a notable modern feature, reportedly weighing around 25 tonnes and containing several thousand pipes. It has since been expanded and modified, including the addition of French-style horizontal trumpet pipes (chamades) and further work on its lowest registers, reflecting the cathedral's continuing role as a venue for organ music.