We present new ultra-metal-poor (UMP) stars parameters with [Fe/H]<-4.0 based on line-by-line non-local thermodynamic equilibrium (NLTE) abundances using an up-to-date iron model atom with a new recipe for non-elastic hydrogen collision rates. We study the departures from LTE in their atmospheric parameter and show that they can grow up to ~1.0 dex in [Fe/H], 150K in Teff and 0.5 dex in log g toward the lowest metallicities. Accurate NLTE atmospheric stellar parameters, in particular [Fe/H] being signifcantly higher, are the first step to eventually providing full NLTE abundance patterns that can be compared with Population III supernova nucleosynthesis yields to derive properties of the first stars. Overall, this maximizes the potential of these likely second-generation stars to investigate the early universe and how the chemical elements were formed.