Gram-negative bacteria represent a major group of pathogens that infect all eukaryotes from plants to mammals. Gram-negative microbe-associated molecular patterns include lipopolysaccharides and peptidoglycans, major immunostimulatory determinants across phyla. Recent advances have furthered our understanding of Gram-negative detection beyond the well-defined pattern recognition receptors such as TLR4. A B-type lectin receptor for LPS and Lysine-motif containing receptors for peptidoglycans were recently added to the plant arsenal. Caspases join the ranks of mammalian cytosolic immune detectors by binding LPS, and make TLR4 redundant for septic shock. Fascinating bacterial evasion mechanisms lure the host into tolerance or promote inter-bacterial competition. Our review aims to cover recent advances on bacterial messages and host decoding systems across phyla, and highlight evolutionarily recurrent strategies.