In this article we consider exceptional sequences of invertible sheaves on smooth complete rational surfaces. We show that to every such sequence one can associate a smooth complete toric surface in a canonical way. We use this structural result to prove various theorems on exceptional and strongly exceptional sequences of invertible sheaves on rational surfaces. We construct full strongly exceptional sequences for a large class of rational surfaces. For the case of toric surfaces we give a complete classification of full strongly exceptional sequences of invertible sheaves.
