Some demonstrative embodiments include apparatuses, systems and/or methods of negotiating a range measurement protocol. For example, an initiator station may be configured to transmit a negotiation request message to a responder station and receive a negotiation response message from the responder station to negotiate a range measurement protocol to perform a range measurement procedure with the responder station, the negotiation request message including an initiator protocol element including an indication of one or more initiator range measurement protocols supported by the initiator station, the negotiation response message including a compatibility indication to indicate whether or not at least one of the initiator range measurement protocols is compatible with at least one responder range measurement protocol supported by the responder station; and based on the compatibility indication, select to perform the range measurement procedure with the responder station or to abort communication with the responder station.