Example methods are provided for a network management entity to perform query failure diagnosis in a software-defined networking (SDN) environment. The method may comprise receiving a request to diagnose a query failure; and generating and sending control information to a host to cause the host to inject, at a first network element, a diagnostic packet for transmission along a datapath to a query failure via multiple second network elements. The diagnostic packet may be a query configured according to a query protocol supported by the query server. The method may also comprise: receiving report information associated with the diagnostic packet from at least one of the following: the first network element, the multiple second network elements and the query failure; and based on the report information, determining a diagnosis result associated with the query failure.