Nach guten Platzierungen und dem Gewinn einer Silbermedaille auf der Langdistanz bei den Junioren-Weltmeisterschaften 1991 in Berlin und 1992 in Jyväskylä wurde Terkelsen für die dänische Nationalmannschaft nominiert. 1993 nahm er in West Point bei seiner ersten Weltmeisterschaft teil und wurde dabei unter anderem Zehnter auf der Kurzdistanz. Die erfolgreichste Zeit hatte Terklsen 1997 und 1998. Im norwegischen Grimstad wurde er 1997 zusammen mit Torben Skovlyst, Carsten Jørgensen und Allan Mogensen in der dänischen Staffel Weltmeister. 1998 gewann er den Gesamtweltcup nach Einzelsiegen im Lake District, in Krakau und im estnischen Otepää. 1997 und 1998 wurde er zudem jeweils Dritter im Endklassement der Park World Tour. Mit dem norwegischen Klub Halden SK gewann er außerdem in beiden Jahren die Jukola. Ein dritter Sieg folgte 2000. Nach diesen Erfolgen startete er erst 2003 wieder bei internationalen Meisterschaften. Es gelang ihm im Anschluss wieder an die Weltspitze heranzulaufen, etwa mit einem fünften Platz bei den Heim-Europameisterschaften 2004 auf der Mitteldistanz. 2005 gewann er den Springcup. Bei den Weltmeisterschaften 2005 im japanischen Aichi wurde er auf der Mitteldistanz Vizeweltmeister hinter Thierry Gueorgiou aus Frankreich. 2006 lief er seine letzte internationale Meisterschaftssaison, erreichte aber bei seinen vier Einzelstarts bei den Europa- und Weltmeisterschaften keine Top-Ten-Platzierungen mehr.
Terkelsen ist 1,90 m groß und wog zu Wettkampfzeiten 78 bis 79 kg. Er startete während seiner Karriere für die Vereine Farum OK bzw. Farum/Tisvilde, OK Gorm, IFK Göteborg, Halden SK und IFK Lidingö. Er ist Mitgründer und Miteigentümer der Firma TracTrac, die Software für das Livetracking via GPS herstellt.
