A system and method are provided for implementing unique multi-band service discovery protocols between communicating devices, including wireless communicating devices supporting operations according to multiple standards and in different frequency bands, particularly in peer-to-peer or ad hoc networking schemes. The disclosed systems and methods define within each service discovery frame, whether a service discovery query or a service discovery response, an indication of the frequency band and/or channel that may support a specific service indicated by the service discovery frame. Cooperating communicating devices between which communications are to be established supporting a specific service protocol are provided with a mechanism by which to identify which common frequency bands and/or channels the communicating devices may communicate in executing the specific service.