Należy pisać pałac Na Wodzie (w Łazienkach w Warszawie). Tak podaje Wielki słownik ortograficzny PWN pod redakcją E. Polańskiego (Warszawa 2017, s. 831, hasło pałac). Słowo pałac jest tutaj nazwą gatunkową (rodzajową) i dlatego zapisuje się je małą literą. Nazwą własną pozostaje wyrażenie Na Wodzie, stąd zarówno w przyimku, jak i w formie miejscownikowej wielka litera.
Dodajmy, że tak samo zapisuje się synonimy nazwy pałac Na Wodzie, czyli pałac Na Wyspie i pałac Łazienkowski (kiedyś jeszcze funkcjonowała nieco zwyczajowa nazwa Łazienka Lubomirskiego).
Niestety, nie wszyscy o tym wiedzą. Niezwykle często spotyka się błędny zapis Pałac na Wodzie (np. Początki dzisiejszego Pałacu na Wyspie sięgają końca XVII w. Na polecenie księcia Stanisława Herakliusza Lubomirskiego, jednego z największych polityków, pisarzy i filozofów tych czasów, wybudowana została łaźnia czy Po tym, jak wygląda Pałac na Wyspie, ocenia się stan całych Łazienek).