A study on the physical and mechanical properties of beeswax (BW), candelilla wax (CW), paraffin wax (PW) and blends was carried out with the aim to evaluate their usefulness as coatings for cheeses. Waxes were analyzed by X-ray diffraction (XRD), Fourier Transform Infrared Spectroscopy (FTIR), differential scanning calorimetry (DSC), permeability, viscosity, flexural and tensile tests and scanning electron microscopy. Cheeses were coated with the waxes and stored for 5 weeks at 30 °C. Measured parameters were weight, moisture, occurrence and degree of fractures, and dimensional changes. The crystal phases identified by XRD for the three waxes allowed them to determine the length of alkanes and the nonlinear compounds in crystallizable forms in waxes. FTIR spectra showed absorption bands between 1800 and 800 cm−1 related to carbonyls in BW and CW. In DSC, the onset of melting temperature was 45.5 °C for BW, and >54 °C for CW and PW. Cheeses coated with BW did not show cracks after storage. Cheeses coated with CW and PW showed microcraks, and lost weight, moisture and shrunk. In the flexural and tensile tests, BW was ductile; CW and PW were brittle. BW blends with CW or PW displays a semi ductile behavior. Cheeses coated with BW blends lost less than 5% weight during storage. The best waxes were BW and the blends.