Ingólfur Arnarson was de eerste kolonist die zich permanent op IJsland vestigde. Toen hij de zuidkust van IJsland naderde, gooide hij naar destijds vigerend heidens gebruik, twee heilige, aan de Noorse god Thor, gewijde houten balken, de Öndvegissúlur, overboord en zwoer dat hij zijn boerderij zou bouwen op de plaats waar ze aan land zouden spoelen. Zijn slaven vonden ze een paar jaar later terug aan de zuidwestkust van de baai Faxaflói. Hij vestigde zich er omstreeks 877. Hij noemde de plek Reykjavík, Rookbaai, omdat hij stoom zag oprijzen uit de hete bronnen in de omgeving. Reykur betekent rook, að reykja roken en vík is kleine baai of inham. De boerderij van Íngólfur stond waarschijnlijk ongeveer op de plek tussen het tegenwoordige stadhuis en de oude haven. Aan de Aðalstræti bevindt zich nu een put waarvan wordt gedacht dat Ingólfur op die plaats zijn water haalde. Een standbeeld van hem is te zien bij Lækjartorg.

In 2001 is bij werkzaamheden in Reykjavík een oud langhuis uit 871 gevonden. Het huis heeft zijn eigen museum gekregen, het Reykjavík 871±2 (verwijzend naar de datering van een vondst met een foutmarge van twee jaar).

De kolonisatie van IJsland wordt uitvoerig beschreven in het oude IJslandse Landnámabók, Boek der Landname. Het stichten van de eerste nederzetting wordt ook genoemd in het Íslendingabók, Boek van de IJslanders. Verder wordt Reykjavik in de middeleeuwse IJslandse literatuur eigenlijk niet genoemd, behalve her en der als landbouwgrond of als woonoord, bijvoorbeeld in hoofdstuk 10 in de Holmsveria saga ofwel de saga van Hord. Wel worden in het Þjóðmenningarhúsið originele IJslandse manuscripten, zoals het Flateyjarbók, de Edda, het Íslendingabók en saga's bewaard. Ook het Landnámabók wordt hier bewaard.

Reykjavik bestond aanvankelijk als een dorp uit een handvol boerderijen, maar rond het midden van de 18e eeuw begon deze kleine gemeenschap zich uit te breiden rond de wolververij en -weverij en touwfabriek van sheriff Skúli Magnússon. Van hem staat nu een standbeeld op de hoek van de Aðalstræti en Kirkjustræti. Toen Reykjavík in 1786 stadsrechten kreeg, waren er ongeveer 170 inwoners. Hierna groeide het stadje langzaam maar zeker en binnen een paar decennia verhuisden de regeringszetels en de onderwijsinstanties erheen, of werden er ingesteld, zoals het Alding, het parlement van þingvellir, het hooggerechtshof, de bisschopszetel, de Latijnse school en de theologische school. In 1844 werd de enige drukpers in het land verplaatst van het eilandje Viðey naar Reykjavik. De Universiteit van IJsland werd in 1911 in Reykjavik opgericht.

Reykjavik heeft een moderne, 20e-eeuwse kerk, de Hallgrímskirkja, die boven de stad uitsteekt. Deze kerk behoort tot de Evangelisch-Lutherse Kerk, de Nationale Kerk van IJsland of Volkskerk, waartoe 93 % van de bevolking behoort. Dit kerkgebouw is naar Hallgrímur Pétursson (1614-1675) genoemd , de grootste hymnenschrijver van het land, wiens werk nog vaak ten gehore wordt gebracht. De architect van de kerk, Guðjón Samúelsson, heeft zich laten inspireren door de grote basaltpartijen die op IJsland zijn te vinden. De bouw heeft 49 jaar geduurd. In 1986 was de kerk gereed. De grote klok in de toren draagt de tekst Eysbouts Atensis me fecit en is gegoten door de Klokkengieterij Eijsbouts in Asten.

Sinds 1968 is Reykjavik de zetel van het bisdom Reykjavik, een immediaat bisdom van de Rooms-Katholieke Kerk, waartoe 3 % van de bevolking behoort. Van 1996 tot 2007 stond dit onder leiding van de Limburgse bisschop Joannes Gijsen. De kathedrale kerk, de ook door Guðjón Samúelsson ontworpen Landakotskirkja, werd gebouwd in de jaren 1920 als vervanging van een in 1897 gebouwd kerkgebouw en bevat onder meer een uit de 14e eeuw daterend Mariabeeld en houtsnijwerk van de IJslandse kunstenaar Ríkharður Jónsson. Ook van deze toren is de grote klok gegoten door Eijsbouts in Asten.

In 1986 vonden in Reykjavik de besprekingen plaats tussen president Ronald Reagan van de Verenigde Staten en zijn collega Michail Gorbatsjov van de toenmalige Sovjet-Unie. Hoewel er toen geen overeenkomst of verdrag werd gesloten, betekenden deze besprekingen het einde van de Koude Oorlog.