A mobile ad hoc network (MANET) consists of mobile nodes communicating over wireless channels. Routing in MANETs is very challenging due to the random mobility of nodes and unreliability of wireless channels. Therefore most of the existing routing algorithms make only the best effort to find routes for communication but do not provide any performance guarantee. Because of the widespread use of MANETs in real-time applications, it becomes pertinent to provide deterministic network behavior. Quality of Service (QoS) aims to shape the network behavior and provide performance guarantees. In this work, a novel heuristic called Advanced-Optimised Link State Routing (A-OLSR) protocol is designed to provide QoS. It functions by enhancing the connectivity of nodes and establishing more stable routes as compared to standard best-effort Optimised Link State Routing (OLSR) protocol. The simulation results show that A-OLSR provides lower delay, reduces energy consumption and achieves higher throughput without introducing any additional routing overhead as compared to the standard OLSR and it’s variants-A $$'$$ ′ -OLSR and A $$''$$ ′ ′ -OLSR. The results also show that A-OLSR provides scalability since it’s performance remains consistent with the increasing size of network.