Randomly pick a host from a list, subject to an uptime requirement
Naming  


by calling pickRandomMachine() where I pass a List&lt;MachineInfo&gt; I would assume that I will get a MachineInfo. Better name it to getRandomMachineHostName()  
if you name the parameter holding the List machines you should rename info to machine.  
hostname should be hostName, because it is camelCase casing for variable names.


General  


A Random should be created once and be reused.  
You should place and use the String hostname inside the loop, to remove the need to accessing machine two times.  
You should extract the shuffeling of the machines to a separate method.  
By returning out of the loop we can reverse the if condition  


Refactoring  

Implementing the above will lead to  

public static String getRandomMachineHostName(List&lt;MachineInfo&gt; machines) {

    shuffleMachines(machines);

    for (MachineInfo machine : machines) {
        String hostName = machine.getHostName();
        if (checkHostUptime(hostName)) {
            return hostName;
        }
    }

    return null;
}

private static Random random = new Random(System.nanoTime());
private static void shuffleMachines(List&lt;MachineInfo&gt; machines) {
    Collections.shuffle(machines, random);
}