A new genus, Alanlewisia, of the family Caligidae is established to accommodate a sea louse species originally, but tentatively, placed in the genus Lepeophtheirus by Lewis (1967). The type species is Alanlewisia fallolunulus (Lewis, 1967) comb. n., which is redescribed in detail based on new material collected from bluespine unicornfish, Naso unicornis (Forsskål), caught off New Caledonia in the South Pacific. This species was originally described by Lewis (1967) under the binomen Lepeophtheirus? fallolunulus from the same host species collected in Hawaii. This species was subsequently transferred to the genus Anuretes by Ho and Lin (2000). Lewis was uncertain of the generic placement primarily because of the possession, in the females only, of paired lunule-like structures on the ventral surface of the modified frontal plates. In both sexes the first swimming leg is biramous, with a well-developed endopod bearing 2 long, sparsely-plumose setae, and the third leg has a 2-segmented exopod. This combination of characters serves to differentiate the new genus from existing genera. Preliminary phylogenetic analysis suggests that the new genus represents an early offshoot from the main caligid lineage, basal to the Paralebion-Tuxophorus-Caligus clade identified by Boxshall and Justine (2005).