Car-Parrinello molecular dynamics (CPMD) calculations are presented for a Na+(Phe) complex in aqueous solution and for various stable Na+(Phe) complexes and Na+(H2O)n clusters in the gas phase (with up to six water molecules). The CPMD results are compared to available experimental and ab initio reference data, to DFT results obtained with various combinations of density functionals and basis sets, and to previous classical mechanics MD simulations. The agreement with the reference data in the gas phase validates the CPMD method, showing that it is a valid approach for studying these systems and that it describes correctly the competing Na+-Phe and Na+-H2O interactions. Analysis of MD trajectories reveals that the Na+(Phe) complex in aqueous solution maintains a stable configuration in which the Na+ cation hovers above the phenyl ring, at an average distance of 3.85 angstrom from the ring center, while remaining strongly bound to one of the carboxylic oxygens of Phe. Constrained MD simulations indicate that the free energy barrier opposing dissociation of the complex exceeds 5.5 kcal/mol. We thus confirm that "cation-pi" interactions between alcali cations and the pi ring, combined with other kinds of interactions, may allow aromatic amino acids to overcome the competition with water in binding a cation.