A speech enhancement apparatus and method and a computer-readable recording medium having a program recorded thereon execute a speech enhancement method. The speech enhancement apparatus includes a spectrum subtraction unit generating a subtracted spectrum by subtracting an estimated noise spectrum from a received speech spectrum, a correction function modeling unit generating a correction function to minimize a noise spectrum using variation of a noise spectrum included in training data, and a spectrum correction unit generating a corrected spectrum by correcting the subtracted spectrum using the correction function.