Sialic acids are found on all vertebrate cell surfaces and are part of a larger class of molecules known as nonulosonic acids. Many bacterial pathogens synthesize related nine-carbon backbone sugars; however, the role(s) of these non-sialic acid molecules in host-pathogen interactions is poorly understood. Vibrio vulnificus is the leading cause of seafood-related death in the United States due to its ability to quickly access the host bloodstream, which it can accomplish through gastrointestinal or wound infection. However, little is known about how this organism persists systemically. Here we demonstrate that sialic acid-like molecules are present on the lipopolysaccharide of V. vulnificus, are required for full motility and biofilm formation, and also contribute to the organism's natural resistance to polymyxin B. Further experiments in a murine model of intravenous V. vulnificus infection demonstrated that expression of nonulosonic acids had a striking benefit for bacterial survival during bloodstream infection and dissemination to other tissues in vivo. In fact, levels of bacterial persistence in the blood corresponded to the overall levels of these molecules expressed by V. vulnificus isolates. Taken together, these results suggest that molecules similar to sialic acids evolved to facilitate the aquatic lifestyle of V. vulnificus but that their emergence also resulted in a gain of function with lifethreatening potential in the human host.