This article presents a k-means clustering and weighted k-nearest neighbor (k-NN) regression-based algorithm for the protection of transmission line. Three-phase current signals of both the terminals are synchronized and sampled with a sampling frequency of 3.84 kHz. Cumulative differential sum (CDS) is computed by subtracting the samples of current cycle from the previous cycle at both the terminals of transmission line. k-means clustering is applied on CDS to compute two centroids using moving window of width, equal to one cycle. Difference between the absolute values of centroids is computed at both the terminals and represented by the centroid difference (CD). The CD of both the terminals is added to compute the fault index. The computed fault index is used to detect and classify the types of faults. The location of the fault is estimated by the weighted k-NN regression method. Various case studies are performed to validate the robustness of the algorithm for different fault parameters such as fault impedance and fault location. The effect of noise is also considered to check the accuracy of the proposed algorithm in the noisy environment.