In this paper, a diagnosis algorithm for arteriovenous fistula (AVF) stenosis is developed based on auscultatory features, signal processing, and machine learning. The AVF sound signals are recorded by electronic stethoscopes at pre-defined positions before and after percutaneous transluminal angioplasty (PTA) treatment. Several new signal features of stenosis are identified and quantified, and the physiological explanations for these features are provided. Utilizing support vector machine method, an average of 90% two-fold cross-validation hit-rate can be obtained, with angiography as the gold standard. This offers a non-invasive easy-to-use diagnostic method for medical staff or even patients themselves for early detection of AVF stenosis.