A push to talk message protocol operating on a communication network between an originating and terminating communication device operates to transmit compressed message formats to initiate the push to talk message protocol. Four compressed session protocol message formats are used in the preferred embodiment. A compressed originating session initiation invite message is transmitted from the originating mobile station. A compressed terminating session initiation invite message is received by the terminating mobile station. A compressed session initiation protocol ping message is transmitted from the originating mobile station and received by the terminating mobile station. A compressed 200 OK session initiation protocol message is transmitted from the terminating mobile station and received by the originating mobile station. Finally, the originating mobile decompresses the 200 OK session initiation protocol message. These compressed messages are used to initiate the push to talk communication session.