Highly vesiculated Pseudoalteromonas piscicida strains DE1-A and DE2-A were isolated from seawater and show bactericidal properties toward Vibrio vulnificus and other Gram-positive and Gram-negative bacteria. Here, we report the complete genome sequences of these two P. piscicida strains and identify proteolytic enzymes potentially involved in their antibacterial properties.