In this paper, we propose a new defog algorithm based on fog veil subtraction to remove fog from a single image. The proposed algorithm first estimates the illumination component of the image by applying smoothing to the degraded image, and then obtains the uniform distributed fog veil through a mean calculation of the illumination component. Next, we multiply the uniform veil by the original image to obtain a depth-like map and extract its intensity component to produce a fog veil whose distribution is according with real fog density of the scene. Once the fog veil is calculated, the reflectance map can be obtained by subtracting the veil from the degraded image. Finally, we apply an adaptive contrast stretching to the reflectance map to obtain an enhanced result. This algorithm can be easily extended to video domains and is verified by both real-scene photographs and videos.