This paper addresses the problem of noise removal in X-ray medical images. A novel scheme for image denoising is proposed, by leveraging recent advances in sparse and redundant representations. The noisy X-ray image is decomposed, with respect to an overcomplete dictionary which is either fixed or trained on the noisy image, and it is reconstructed using greedy techniques. The new scheme has been tested with both artificial and real X-ray images and it turns out that it may offer superior denoising results as compared to other existing methods.