We highlight the importance of carrier-phonon coupling in inorganic lead halide perovskite nanocrystals. The low-temperature photoluminescence (PL) spectrum of CsPbBr3 has been investigated under a nonresonant and a nonstandard, quasi-resonant excitation scheme, and phonon replicas of the main PL band have been identified as due to the Fröhlich interaction. The energy of longitudinal optical (LO) phonons has been determined from the separation of the zero phonon band and phonon replicas. We reason that the observed LO phonon coupling can only be related to an orthorhombically distorted crystal structure of the perovskite nanocrystals. Additionally, the strength of carrier-phonon coupling has been characterized using the ratio between the intensities of the first phonon replica and the zero-phonon band. PL emission from localized versus delocalized carriers has been identified as the source of the observed discrepancies between the LO phonon energy and phonon coupling strength under quasi-resonant and nonresonant excitation conditions, respectively.