Format negotiation for media remoting involves at least one media data format. In an example embodiment, a media format negotiation for playing media data is begun between a server and a client. The media data format is transferred from the server to the client. A notification that indicates if an attempt at the client to construct a media topology responsive to the media data format was a success or a failure is transferred from the client to the server. Whether and/or how the media data is to be transferred from the server to the client may be impacted by the notification.