Aspects of the subject matter described herein relate to selecting a source interface with which to establish a connection. In aspects, a profile for each network location a host has seen is maintained in a data store. The profile includes information about the network interfaces available to a source host at the network location. This information indicates, among other things, the reliability of each interface of the source host. Based on the profile, an interface is selected with which to establish a connection. If the interface is unsuccessful in establishing the connection, the interface is de-prioritized and another interface may be selected.