HTTP Adaptive Streaming (HAS) has become the de facto standard technology for the delivery of video streaming services. Current adaptation heuristics for HAS focus on the selection of the optimal quality representation to be delivered from a single server. However, many content providers use multiple content servers storing replicas of the segmented video or are deployed over Content Delivery Networks (CDNs). Hence, the problem is not limited to selecting the optimal quality but also consists in requesting the segments from the best performing video server. In this paper a dynamic server selection strategy is proposed that enables the streaming client to select the optimal video delivery server. The proposed mechanism allows any quality adaptation algorithm to be plugged into it. The selection algorithm uses probability-based search strategies to explore the search space of available servers and to gain insights in their characteristics. This prevents the selection strategy to end up in a local optimum. To avoid buffer starvations, the exploration behavior is dependent on the current buffer filling. The proposed approach allows to achieve a Quality of Experience (QoE) that is within 25% of the optimum for which the client has a priori knowledge of the server characteristics.