This disclosure is directed to techniques for video call setup in a mobile video telephony network. In general, the call setup techniques reduce call setup delays by preemptively retransmitting NSRP packets before expiration of the timeout period ordinarily required for receipt of an NSRP ACK packet from the remote terminal. The retransmitted NSRP packets may be retransmitted during idle periods in which the modem layer in the sending mobile terminal has received no other data for transmission of the remote mobile terminal, thereby taking advantage of idle bandwidth. Multiplex data received by the modem can be locally buffered at the modem layer for retransmission. In this manner, retransmission does not require regeneration of the original call setup messages nor multiplexing. Instead, the previously generated and multiplexed data is buffered at the modem layer for retransmission to reduce processing overhead within the mobile terminal.