The probiotic industry faces the challenge of retention of probiotic culture viability as numbers of these cells within their products inevitably decrease over time. In order to retain probiotic viability levels above the therapeutic minimum over the duration of the product’s shelf life, various methods have been employed, among which encapsulation has received much interest. In line with exploitation of encapsulation for protection of probiotics against adverse conditions, we have previously encapsulated bifidobacteria in poly-(vinylpyrrolidone)-poly-(vinylacetate-co-crotonic acid) (PVP:PVAc-CA) interpolymer complex microparticles under supercritical conditions. The microparticles produced had suitable characteristics for food applications and also protected the bacteria in simulated gastrointestinal fluids. The current study reports on accelerated shelf life studies of PVP:PVAc-CA encapsulated Bifidobacterium lactis Bb12 and Bifidobacterium longum Bb46. Samples were stored as free powders in glass vials at 30 °C for 12 weeks and then analysed for viable counts and water activity levels weekly or fortnightly. Water activities of the samples were within the range of 0.25–0.43, with an average a w = 0.34, throughout the storage period. PVP:PVAc-CA interpolymer complex encapsulation retained viable levels above the recommended minimum for 10 and 12 weeks, for B. longum Bb46 and B. lactis Bb12, respectively, thereby extending their shelf lives under high storage temperature by between 4 and 7 weeks. These results reveal the possibility for manufacture of encapsulated probiotic powders with increased stability at ambient temperatures. This would potentially allow the supply of a stable probiotic formulation to impoverished communities without proper storage facilities recommended for most of the currently available commercial probiotic products.