We study the problem of restoring severely degraded face images such as images scanned from passport photos or images subjected to fax compression, downscaling, and printing. The purpose of this paper is to illustrate the complexity of face recognition in such realistic scenarios and to provide a viable solution to it. The contributions of this work are two-fold. First, a database of face images is assembled and used to illustrate the challenges associated with matching severely degraded face images. Second, a preprocessing scheme with low computational complexity is developed in order to eliminate the noise present in degraded images and restore their quality. An extensive experimental study is performed to establish that the proposed restoration scheme improves the quality of the ensuing face images while simultaneously improving the performance of face matching.