Using transient Rayleigh scattering (TRS) measurements, we obtain photoexcited carrier thermalization dynamics for both zincblende (ZB) and wurtzite (WZ) InP single nanowires (NW) with picosecond resolution. A phenomenological fitting model based on direct band to band transition theory is developed to extract the electron-hole-plasma density and temperature as a function of time from TRS measurements of single nanowires which have complex valence band structures. We find that the thermalization dynamics of hot carriers depends strongly on material (GaAs NW vs. InP NW) and less strongly on crystal structure (ZB vs. WZ). The thermalization dynamics of ZB and WZ InP NWs are similar. But a comparison of the thermalization dynamics in ZB and WZ InP NWs with ZB GaAs NW reveals more than an order of magnitude slower relaxation for the InP NWs. We interpret these results as reflecting their distinctive phonon band structures which lead to different hot phonon effects. Knowledge of hot carrier thermalization dynamics is an essential component for effective incorporation of nanowire materials into electronic devices.