In this paper, we discuss the general significance of order in physics, as a first step toward the development of new notions of order. We begin with a brief historical discussion of the notions of order underlying ancient Greek views, and then go on to show how these changed in key ways with the rise of classical physics. This leads to a broader view of the significance of order, which helps to indicate what is to be meant by a change (...) of our general notions of order in physics. We then go into relativity and quantum theory, showing how these developments actually did bring in further new notions of order, which are however inconsistent and otherwise inadequate in certain ways. Finally, using these inconsistencies and inadequacies as clues or indications for yet a further new concept of order, we make some proposals for novel directions of inquiry (to be discussed in some detail in later papers) which could lead to theories as different from relativity and quantum theory as these are from classical physics. (shrink)