Phlebotomine sand flies that transmit the protozoan parasite Leishmania differ greatly in their ability to support different parasite species or strains in the laboratory: while some show considerable selectivity, others are more permissive. In "selective" sand flies, Leishmania binding and survival in the fly midgut typically depends upon the abundant promastigote surface adhesin lipophosphoglycan (LPG), which exhibits species- and strain-specific modifications of the dominant phosphoglycan (PG) repeat units. For the "selective" fly Phlebotomus papatasi PpapJ, side chain galactosyl-modifications (scGal) of PG repeats play key roles in parasite binding. We probed the specificity and properties of this scGal-LPG PAMP (Pathogen Associated Molecular Pattern) through studies of natural isolates exhibiting a wide range of galactosylation patterns, and of a panel of isogenic L. major engineered to express similar scGal-LPG diversity by transfection of SCG-encoded β1,3-galactosyltransferases with different activities. Surprisingly, both 'poly-scGal' and 'null-scGal' lines survived poorly relative to PpapJ-sympatric L. major FV1 and other 'mono-scGal' lines. However, survival of all lines was equivalent in P. duboscqi, which naturally transmit L. major strains bearing 'null-scGal'-LPG PAMPs. We then asked whether scGal-LPG-mediated interactions were sufficient for PpapJ midgut survival by engineering Leishmania donovani, which normally express unsubstituted LPG, to express a 'PpapJ-optimal' scGal-LPG PAMP. Unexpectedly, these "L. major FV1-cloaked" L. donovani-SCG lines remained unable to survive within PpapJ flies. These studies establish that midgut survival of L. major in PpapJ flies is exquisitely sensitive to the scGal-LPG PAMP, requiring a specific 'mono-scGal' pattern. However, failure of 'mono-scGal' L. donovani-SCG lines to survive in selective PpapJ flies suggests a requirement for an additional, as yet unidentified L. major-specific parasite factor(s). The interplay of the LPG PAMP and additional factor(s) with sand fly midgut receptors may determine whether a given sand fly host is "selective" or "permissive", with important consequences to both disease transmission and the natural co-evolution of sand flies and Leishmania.