Lemon myrtle, anise myrtle, and Tasmanian pepper leaf are commercial Australian native herbs with a high volatile or essential oil content. Packaging of the herbs in high- or low-density polyethylene (HDPE and LDPE) has proven to be ineffective in preventing a significant loss of volatile components on storage. This study investigates and compares the effectiveness of alternate high-barrier property packaging materials, namely, polyvinylidene chloride coated polyethylene terephthalate/casted polypropylene (PVDC coated PET/CPP) and polyethylene terephthalate/polyethylene terephthalate/aluminum foil/linear low-density polyethylene (PET/PET/Foil/LLDPE), in prevention of volatile compound loss from the three native herbs stored at ambient temperature for 6 months. Concentrations of major volatiles were monitored using gas chromatography-mass spectrometry (GC-MS) techniques. After 6 months of storage, the greatest loss of volatiles from lemon myrtle was observed in traditional LDPE packaging (87% loss) followed by storage in PVDC coated PET/CPP (58% loss) and PET/PET/Foil/LLDPE (loss of 23%). The volatile loss from anise myrtle and Tasmanian pepper leaf stored in PVDC coated PET/CPP and PET/PET/Foil/LLDPE packaging was <30%. This study clearly indicates the importance of selecting the correct packaging material to retain the quality of herbs with high volatile content.