Technological advancements have led to increased confidence in the design of large-scale wireless networks that comprise small energy constraint devices. Despite the boost in technological advancements, energy dissipation and fault tolerance are amongst the key deciding factors while designing and deploying wireless sensor networks. This paper proposes a Fault-tolerant Energy-efficient Hierarchical Clustering Algorithm (FEHCA) for wireless sensor networks (WSNs), which demonstrates energy-efficient clustering and fault-tolerant operation of cluster heads (CHs). It treats CHs as no special node but equally prone to faults as normal sensing nodes of the cluster. The proposed scheme addresses some of the limitations of prominent hierarchical clustering algorithms, such as the randomized election of the cluster heads after each round, which results in significant energy dissipation; non-consideration of the residual energy of the sensing nodes while selecting cluster heads, etc. It utilizes the capability of vector quantization to partition the deployed sensors into an optimal number of clusters and ensures that almost the entire area to be monitored is alive for most of the network’s lifetime. This supports better decision-making compared to decisions made on the basis of limited area sensing data after a few rounds of communication. The scheme is implemented for both friendly as well as hostile deployments. The simulation results are encouraging and validate the proposed algorithm.