Mycobacteriophages are good model systems for understanding their bacterial hosts and show promise as therapeutic agents for nontuberculous mycobacterium infections. However, little is known about phage recognition of Mycobacterium cell surfaces, or mechanisms of phage resistance. We show here that surface-exposed trehalose polyphleates (TPPs) are required for infection of Mycobacterium abscessus and Mycobacterium smegmatis by clinically useful phages BPs and Muddy, and that TPP loss leads to defects in adsorption, infection, and confers resistance. Transposon mutagenesis indicates that TPP loss is the primary mechanism for phage resistance. Spontaneous phage resistance occurs through TPP loss, and some M. abscessus clinical isolates are phage-insensitive due to TPP absence. Both BPs and Muddy become TPP-independent through single amino acid substitutions in their tail spike proteins, and M. abscessus mutants resistant to TPP-independent phages reveal additional resistance mechanisms. Clinical use of BPs and Muddy TPP-independent mutants should preempt phage resistance caused by TPP loss.