Vid Carl Milles skulptur Fem musicerande genier låg tidigare ett badhus. Det byggdes 1843 och hade till en början två stora bassänger i ån. I badhuset fanns duschar och badkar, med både varmt och kallt vatten. Under badbesöket hade badgästerna inte bara tillgång till handdukar och varma tofflor, utan också hårkammar. Badhusets kafé hade servering på ett av taken, med utsikt över Gavleån och de två bassängerna. Det var kring badhuset som de tidigaste delarna av Stadsträdgården växte fram. Tegelhagen eller Strömparterren, som området ursprungligen kallades, anlades med slingrande gångvägar runt gräsytor planterade med blomstergrupper.
Med åren utökades badhuset med ytterligare en bassäng. Trots att badhuset inte fick användas till annat ändamål än badhusinrättning, fanns här åtta enkla rum för uthyrning. I samband med att kvarteret fick namnet Najaden på 1920-talet, fick badhuset samma namn. Vid den tiden hade badhuset börjat förfalla. På 1940-talet var badhuset i så dåligt skick att kaférörelsen förbjöds i vissa delar av byggnaden. 1956 revs badhuset.
På andra sidan Gavleån byggdes Gävles nya badhus, Strömbadet, som invigdes 1960.
På Länsmuseet Gävleborgs webbplats kan du se en karta som visar var Gävleskyltarna är utplacerade.