Steinsson was in de zomer van 2005 de grote onbekende op de Alkmaarderhout. De IJslandse rechtsback, overgekomen van het ZwitserseYoung Boys, moest bij het AZ van Louis van Gaal de naar Villarreal vertrokken Jan Kromkamp doen vergeten en mocht na een maand voor het eerst in de basis beginnen als vervanger voor Kew Jaliens in de met 5-3 verloren Europese wedstrijd tegen Krylia Sovetov Samara. In het daaropvolgende seizoen werd hij een vaste waarde voor AZ als rechtsback, waardoor Kew Jaliens in het centrum ging spelen. Op 15 januari2008 kwamen AZ en Bolton Wanderers tot een overeenkomst over de transfer van Steinsson, waarbij Bolton zijn contract voor ruim vijf miljoen euro heeft afgekocht. Na bijna vijf seizoenen in Engeland vertrok Steinsson in 2012 naar Kayserispor, waar hij nog een seizoen heeft gespeeld.
Na een reeks wedstrijden voor alle vertegenwoordigende jeugdteams debuteerde Steinsson op 8 maart2002 voor IJsland in een vriendschappelijkeInterland uit tegen Brazilië. Hij scoorde als invaller slechts zeventien minuten nadat hij in het veld was gekomen, IJsland verloor de wedstrijd uiteindelijk wel met 6-1. Steinsson kwam uiteindelijk tot 46 interlands, waarin hij viermaal scoorde.
IJsland
ÍA Akranes (2001)
.svg){kind=small}
Super League
Eredivisie
Premier League
Süper Lig