We define formally the notion of invariant definability in a logic $\cL$ and study it systematically. We relate it to other notions of definability (implicit definability, $\Delta$-definability and definability with built-in relations) and establish connections between them. In descriptive complexity theory, invariant definability is mostly used with a linear order (or a successor relation) as the auxiliary relation. We formulate a conjecture which spells out the special role linear order plays in capturing complexity classes with logics and prove two special cases.