Methods, systems, and computer readable media for early media connection proxying are disclosed. According to one method, a call setup signaling message is received for establishing a call between a calling entity and a called entity. Based on at least one parameter in the call setup signaling message, it is determined whether an early media connection is required for the call. It is also determined whether early media connection proxying is required for the call. In response to determining that an early media connection and early media connection proxying are required for the call, signaling is performed on behalf of a network entity to establish an early media connection for the call.