Within density functional theory, we study bulk band structure and surface states of BiTeBr. We consider both ordered and disordered phases which differ in atomic order in the Te-Br sublattice. On the basis of relativistic ab-initio calculations, we show that the ordered BiTeBr is energetically preferable as compared with the disordered one. We demonstrate that both Te- and Br-terminated surfaces of the ordered BiTeBr hold surface states with a giant spin-orbit splitting. The Te-terminated surface-state spin splitting has the Rashba-type behavior with the coupling parameter alpha_R ~ 2 eVAA.