Due to complex and volatile lighting environment, underwater imaging can be readily impaired by light scattering, warping, and noises. To improve the visual quality, Underwater Image Enhancement (UIE) techniques have been widely studied. Recent efforts have also been contributed to evaluate and compare the UIE performances with subjective and objective methods. However, the subjective evaluation is time-consuming and uneconomic for all images, while existing objective methods have limited capabilities for the newly-developed UIE approaches based on deep learning. To fill this gap, we propose an Underwater Image Fidelity (UIF) metric for objective evaluation of enhanced underwater images. By exploiting the statistical features of these images in CIELab space, we present the naturalness, sharpness, and structure indexes. Among them, the naturalness and sharpness indexes represent the visual improvements of enhanced images; the structure index indicates the structural similarity between the underwater images before and after UIE. We combine all indexes with a saliency-based spatial pooling and thus obtain the final UIF metric. To evaluate the proposed metric, we also establish a first-of-its-kind large-scale UIE database with subjective scores, namely Underwater Image Enhancement Database (UIED). Experimental results confirm that the proposed UIF metric outperforms a variety of underwater and general-purpose image quality metrics. The database and source code are available at https://github.com/z21110008/UIF.