Methods and systems for reducing the latency of instant communication session establishment are presented. According to various preferred embodiments, a RAN, may receive a setup request message via a packet-switched network. The RAN may determine, from a quality of service (QOS) indication contained in the setup request message, that the setup request message is requesting establishment of a instant communication session. The RAN may further determine an intended destination wireless communication device (WCD) for the setup request message. Based on the QOS indication and/or a profile indicating the destination WCD's capabilities, the RAN may pre-allocate resources for the instant communication session in parallel to paging the destination WCD. In this way, the latencies associated with these procedures are overlapped, thus reducing the overall latency of instant communication session establishment.