Instant messaging with audio connection formation is described. In an implementation, a method includes forming a communication to authenticate a client with a proxy during an instant messaging session and forming an invitation by the client for communication to the proxy that identifies another client, with which, to communicate via an audio connection. An acceptance is received from the other client via the proxy to form the audio connection.