We use cosmological simulations from the Aquarius Project to study the orbital history of the Large Magellanic Cloud (LMC) and its potential association with other satellites of the Milky Way (MW). We search for dynamical analogs to the LMC and find a subhalo that matches the LMC position and velocity at either of its two most recent pericentric passages. This suggests that the LMC is not necessarily on its first approach to the MW, provided that the virial mass of the Milky Way is M_200 ~1.8e12 M_sun. The simulation results yield specific predictions for the position and velocity of systems associated with the LMC prior to infall. If on first approach, most should lie close to the LMC because the Galactic tidal field has not yet had enough time to disperse them. If on second approach, the list of potential associates increases substantially. Interestingly, our analysis rules out an LMC association for Draco and Ursa Minor, two of the dwarf spheroidals suggested by Lynden-Bell & Lynden-Bell to form part of the "Magellanic Ghostly Stream". Our results also indicate that the direction of the orbital angular momentum is a powerful test of LMC association. This test, however, requires precise proper motions, which are unavailable for most MW satellites. Of the 4 satellites with published proper motions, only the Small Magellanic Cloud is clearly associated with the LMC. Taken at face value, the proper motions of Carina, Fornax and Sculptor rule them out as potential associates, but this conclusion should be revisited when better data become available. The dearth of satellites clearly associated with the Clouds might be solved by wide-field imaging surveys that target its surroundings, a region that may prove a fertile hunting ground for faint, previously unnoticed MW satellites.