The complex structure of halide and oxide perovskites strongly affects their physical properties. Here, the effect of dimensions reduced 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 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 a 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 ultrasmall perovskite crystals.