Media relay services are often used to establish sufficiently direct connections in order to enable provisioning of a real-time media service and/or improve the quality of real-time media services. However, media relay services are often gated using authentication systems that add undesirable delay to the delivery and/or access to a real-time media service, which in turn diminish the user experience. By contrast, various implementations disclosed herein include apparatuses, systems, and methods of providing low latency authentication of gated media relay services. For example, in some implementations, a method includes receiving a request for access to a gated media relay service, providing provisional access to the service until an authentication result is available, determining whether the requesting device is authorized to access the media relay service, and at least one of ending or continuing access to the media relay service based on the authentication result.