Hylkysaaren nimenä on kartoissa vuodesta 1655 lähtien vaihdellen Kalfholmen, Kallholmen, Kalholmen ja Kahlholmen. Nimi on tarkoittanut joko "kaljua"”kaljua”, puutonta saarta tai läheisen Korkeasaaren viereistä pienempää saarta eli "vasikkaa"”vasikkaa” (ruots. {{k-sv|kalf}} 'vasikka'’vasikka’). Nimi Vrakholmen esiintyy kartoissa 1700-luvun jälkipuoliskolta lähtien. Suomenkieliseksi nimeksi oli jo vuonna 1908 ehdolla Hylkysaari, mutta virallisesti vahvistettiin vuonna 1909 Vrakholma ja vasta vuonna 1928 nykyinen nimi.<ref>Olavi Terho ym. (toim.): ''Helsingin kadunnimet'', s. 102. Helsingin kaupungin julkaisuja 24, 1970, Helsinki.</ref>