Alpheus randalli was first described in 1981 from the Marquesas Islands in the Indian Ocean where it was found living at a depth of 18 meters in association with a previously undescribed species of goby in the genus Amblyeleotris.