Abstract The consensus protocol is the foundation of all blockchain systems. Existing consensus protocols like Proof-of-Work (PoW) consume a vast amount of energy. However, they are severely limited to transaction throughput. Consensus protocols like Proof-of-Stake (PoS) have been proposed to address this challenge. However, these protocols have compromised the fairness by discouraging the “poorer” participants and allowing “richest” stakeholders to have full control over the generation of blocks. Towards meeting these conflicting requirements on throughput and fairness, we propose a blockchain consensus protocol based on the Quality-of-Service (QoS). In our Proof-of-QoS (PoQ) protocol, the entire network is divided into small regions. Each region nominates a node based on its QoS. A deterministic Byzantine Fault Tolerance (BFT) consensus is then run among all nominated nodes. PoQ aims to achieve a very high transaction throughput as a permissionless protocol and provides a fairer environment for participants. Our experimental results show that PoQ can achieve 9.7K transactions per second (TPS) for a network of 12 regions.