We report here the complete genome sequence of a marine Halopseudomonas aestusnigri strain isolated from asphalt sediments of the Gulf of Mexico. Studying the genomes of atypical environmental bacteria increases knowledge about the biology of microorganisms metabolizing pollutants and is also a biotechnological resource to develop bioremediation methods.