Complex structure of halide and oxide perovskites strongly affect their physical properties. Here the effect of reduced dimensions to the nanoscale has been investigated by a combination of single-dot optical experiments with a phase transition theory. Methylammonium lead bromide (CH3NH3PbBr3) nanocrystals with two average particle sizes of ~2 and ~4 nm with blue- and green-photoluminescence, respectively, were spectrally and temporally probed on a single particle level from 5 K to 295 K. The results show that the abrupt blue-shift of the photoluminescence spectra and lifetimes at ~150 K can be attributed to the cubic-to-tetragonal phase transition in the large 4 nm nanocrystals, while this phase transition is completely absent for the small 2 nm particles in the investigated temperature range. Theoretical calculations based on Landau theory reveal strong size-dependent effect on temperature-induced phase transitions in individual CH3NH3PbBr3 nanocrystals, corroborating experimental observations. This effect should be considered in structure-property analysis of ultra-small perovskite crystals.