The Cryogenic Underground Observatory for Rare Events (CUORE) at Laboratori Nazionali del Gran Sasso of INFN in Italy is an experiment searching for neutrinoless double beta (0$\nu\beta\beta$) decay. Its main goal is to investigate this decay in $^{130}$Te, but its ton-scale mass and low background make CUORE sensitive to other rare processes as well. In this work, we present our first results on the search for \nbb decay of $^{128}$Te, the Te isotope with the second highest natural isotopic abundance. We find no evidence for this decay, and using a Bayesian analysis we set a lower limit on the $^{128}$Te \nbb decay half-life of T$_{1/2} > 3.6 \times 10^{24}$ yr (90\% CI). This represents the most stringent limit on the half-life of this isotope, improving by over a factor 30 the previous direct search results, and exceeding those from geochemical experiments for the first time.