CT beam hardening artifacts near metal hip implants may erroneously enhance or diminish radiotracer uptake following CT attenuation correction (AC) of PET images. An artifact reduction algorithm (ARA) was developed to reduce metal artifacts in CT-based AC-PET. The algorithm employed a Bayes classifier to identify beam-hardening artifacts, followed by a partial correction of the attenuation map. ARA was implemented on phantom and patient 18F-FDG studies using a clinical PET/CT scanner. In phantom studies ARA successfully removed two artifacts of erroneously elevated uptake near a stainless steel hip prosthesis which were depicted in the standard CT-AC PET. ARA has also identified two targets absent on the scanner PET images. Target-to-background ratios were 1.5-3 times higher for ARA-PET than scanner images. In a patient study, metal artifacts were of lower intensity in ARA-PET as compared to standard images. Potentially, ARA may improve detectability of small lesions located near metal hip implants.