This work addresses the problem of Quality of Service (QoS) aware sensor allocation for target tracking in a sensor-cloud environment. In a sensor-cloud environment, whenever a target enters within a sensor deployed zone, physical sensor nodes are dynamically scheduled and allocated for the corresponding target. In this work, specifically, we address the issue of selection of an optimal set of sensors to track a particular target. However, in sensor-cloud the underlying physical sensor nodes are heterogeneous with respect to their owner, their sensing ability, transmission range, and the unit cost of usability. Considering the heterogeneity of the nodes, we propose the QoS-aware Sensor Allocation Algorithm (Q-SAA) that takes into account an assortment of parameters that determine QoS. Thereafter, using an auction-based mechanism we find the optimal solution for allocation of a subset of available sensors to achieve efficient target tracking. Experimental results on implementation of our solution show that in comparison with the considered benchmark, the proposed scheme schedules approximately 20–30% less number of sensors for target tracking applications and still achieves the desired QoS while tracking the target.