The purpose of these experiments was to study the physical structure of the nucleocapsid-M protein complex of vesicular stomatitis virus by analysis of nucleocapsid binding by wild-type and mutant M proteins and by limited proteolysis. We used the temperature-sensitive M protein mutant tsO23 and six temperature-stable revertants of tsO23 to test the effect of sequence changes on M protein binding to the nucleocapsid as a function of NaCl concentration. The results showed that M proteins from wild-type, mutant, and three of the revertant viruses had similar NaCl titration curves, while the curve for M proteins from the other three revertants differed significantly. The altered NaCl dependence of M protein was correlated with a single amino acid substitution from Phe to Leu at position 111 compared with the original temperature-sensitive mutant and was not correlated with a substitution of Gly to Glu at position 21 in tsO23 and the revertants. To determine whether protease cleavage sites in the M protein were protected by interaction with the nucleocapsid, nucleocapsid-M protein complexes were subjected to limited proteolysis with trypsin, chymotrypsin, or Staphylococcus aureus V8 protease. The initial trypsin and chymotrypsin cleavage sites, located after amino acids 19 and 20, respectively, were as accessible to proteases when M protein was bound to the nucleocapsid as when it was purified, indicating that this region of the protein does not interact directly with the nucleocapsid. Furthermore, trypsin or chymotrypsin treatment released the M protein fragments from the nucleocapsid, presumably due to conformational changes following proteolysis. V8 protease cleaved the M protein at position 34 or 50, producing two distinct fragments. The M protein fragment produced by V8 protease cleavage at position 34 remained associated with the nucleocapsid, while the fragment produced by cleavage at position 50 was released from the nucleocapsid. These results suggest that the amino-terminal region of the M protein around amino acid 20 does not interact directly with the nucleocapsid and that conformational changes resulting from single-amino-acid substitutions at other sites in the M protein are important for this interaction.