Cold atmospheric plasma (CAP) is used as an emerging technology for food preservation. In this study, CAP treatment has been applied to bakery products for the first time. The aim of the work was to investigate the effect of the use of CAP on the amount of microorganisms during bread storage. Basic physicochemical properties and bread texture were determined during storage for 0, 3, and 6 days. The study material included gluten-free and mixed wheat-rye bread treated with CAP for 2 and 10 min. The results showed that no mesophilic bacteria or fungi were found after ten minutes of the bread exposure to CAP. In addition, only 2-min non-thermal sterilization resulted in complete inhibition of yeast and mould growth in the gluten-free and wheat-rye bread. A decrease in the microbial growth in the bread was noted; however, a simultaneous decrease in the moisture content of the bread was observed. After the application of plasma for 2 or 10 min, both the gluten-free and mixed wheat-rye bread was characterized by reduced humidity, which also resulted in a significant increase in the hardness and a slight increase in the springiness of the bread. The use of CAP in storage of bread is promising; nevertheless, it is necessary to further study the effect of this treatment in bread with improvers, especially with hydrocolloids and fibers.