Bærinn Nauthóll var reistur um árið 1850. Hann var eitt margra nýbýla, sem risu í nágrenni Reykjavíkur þessum tíma. Hann var hjáleiga frá Skildinganesbænum og stóð við fjölfarinn vegaslóða. Taugaveiki kom upp á bænum í kringum aldamótin 1900 og hann var brenndur. Tóftir hans sjást enn þá rétt við flugvallargirðinguna, norðan bílastæðanna.
Í síðari heimsstyrjöldinni voru miklar herbúðir og umsvif á vegum setuliðsins umhverfis flugvöllinn. Í Nauthólsvíkinni var aðstaða fyrir sjóflugvélar, sem voru mikilvægar í orrustunni um Atlantshafið. Þar var m.a. norsk flugsveit. Minnisvarði um veru hennar hér stendur vestan þjónustuhússins.
Á árunum eftir styrjöldina komu upp hugmyndir um nýtingu Nauthólsvíkur sem sjóbaðsstaðar og aðstaðan var bætt en síðar voru sjóböð bönnuð vegna mengunar. Á áttunda áratugnum var síðan heiti lækurinn, sem gekk undir ýmsum nöfnum, vinsæll unz honum var lokað 1985. Þegar hreinsun strandlengju borgarinnar fór á skrið, kviknuðu hugmyndir um að endurvekja Nauthólsvík sem sjóbaðstað og framkvæmdir hófust skömmu síðar. Ströndin var vígð sumarið 2000 og ári síðar var opnuð þjónustumiðstöð með búningsklefum, baðaðstöðu og veitingasölu (ís, sælgæti og gosdrykkir). Við ákjósanlegustu aðstæður er hitastig sjávarlónsins innan grjótgarðanna 18-20°C og pottarnir eru 30-35°C heitir. Lónið og pottarnir eru hitaðir upp með affallsvatni frá hitaveitugeymunum í Öskjuhlíð. Þar er vatn, sem hefur verið nýtt til upphitunar húsa borgarbúa.
Þjónustuhúsið er tilvalin aðstaða fyrir hlaupara, sem geta valið úr miklum fjölda hlaupaleiða, s.s. skógarstígum Öskjuhlíðar og meðfram ströndinni til vesturs og inn Fossvogsdalinn í átt að Elliðavatni.
Ylströndin í Nauthólsvík er annar tveggja baðstaða á landinu, sem hefur fengið „Bláfánann”, alþjóðlega viðurkenningu, sem Landvernd hefur umboð til að veita. Staðir, sem fá þessa vottun, verða að uppfylla ströng skilyrði um hreinlæti, vatnsgæði, öryggi, aðbúnað og fræðslu fyrir gesti og umhverfisvernd. Þess er vænzt, að gestir séu meðvitaðir um gildi og mikilvægi góðrar umgengni og að staðurinn megi auka umhverfisvitund þeirra.
Siglingaklúbburinn Siglunes hefur haft aðstöðu í Nauthólsvík, austan Ylstrandarinnar. Þar er hægt að fá leigðar ýmsar gerðir báta, allt frá árabátum og kanóum upp í einfaldari gerðir seglbáta.
