The church takes its name from the 15th-century Swedish leader Engelbrekt Engelbrektsson and was built after Hedvig Eleonora parish was divided in 1906 to cope with Östermalm's rapid population growth. Wahlman won the 1905–06 architectural competition for the new church and parish house, seeing off a rival design by Ivar Tengbom and Ernst Torulf, and the foundation stone was laid in 1910 in the presence of the Crown Prince. After four years of building, with Wahlman himself acting as site supervisor, the church was consecrated in January 1914 before King Gustaf V and other dignitaries.
The building's red-brown patterned brickwork, steep gabled roofs and hand-hewn granite walls give it a distinctive, sturdy character, blending Art Nouveau with National Romantic style. Wahlman is said to have envisaged the church as a "church of the Sermon on the Mount": the soaring nave vault, some 32 metres high and reportedly the tallest of its kind in Scandinavia, rests on eight pillars each inscribed with one of the Beatitudes. The asymmetrically placed tower rises around 65 metres above its platform, topped with a gilded copper spire likened to a bridal crown, symbolising the congregation as the bride of Christ.
Wahlman himself designed much of the church's furnishings, including the altar fittings, font, silver and textiles. Olle Hjortzberg painted the chancel decoration and the walls of the baptistery on the church's south side, while Tore Strindberg created the stucco reliefs and Filip Månsson the wall paintings. Behind the altar stand seven large silver shields, designed and made by Olga Lanner, said to represent the clouds of heaven; she also created the tall wrought-iron candelabra at the front of the church.
Below the tower, reached from Karlavägen, lies a columbarium opened in 1961 within a former wartime air-raid shelter, holding a large number of burial niches. The church has had several organs over the years; the current instrument, built in 1964 by Grönlunds Orgelbyggeri, is one of the largest in the country, with 86 stops, and the church can seat several hundred worshippers.
The building was well received by contemporaries, with fellow architects praising it as a milestone in Swedish architecture. It underwent a substantial renovation in 1992–93, and further work restored its roof and gilded tower details in the 2010s.