The mycobacterial cell envelope is characterized by the presence of a highly impermeable second membrane, which is composed of mycolic acids intercalated with different unusual free lipids, such as lipooligosaccharides (LOS). Transport across this cell envelope requires a dedicated secretion system for extracellular proteins, such as PE_PGRS proteins, which are specific mycobacterial proteins with polymorphic GC-rich sequence (PGRS). In this study, we set out to identify novel components involved in the secretion of PE_PGRS proteins by screening Mycobacterium marinum transposon mutants for secretion defects. Interestingly, most mutants were not affected in secretion but in the release of PE_PGRS proteins from the cell surface. These mutants had insertions in a gene cluster associated with LOS biosynthesis. Lipid analysis of these mutants revealed a role at different stages of LOS biosynthesis for 10 novel genes. Furthermore, we show that regulatory protein WhiB4 is involved in LOS biosynthesis. The absence of the most extended LOS molecule, i.e. LOS-IV, and a concomitant accumulation of LOS-III was already sufficient to reduce the release of PE_PGRS proteins from the mycobacterial cell surface. A similar effect was observed for major surface protein EspE. These results show that the attachment of surface proteins is strongly influenced by the glycolipid composition of the mycobacterial cell envelope. Finally, we tested the virulence of a LOS-IV-deficient mutant in our zebrafish embryo infection model. This mutant showed a marked increase in virulence as compared with the wild-type strain, suggesting that LOS-IV plays a role in the modulation of mycobacterial virulence.