Lorentz Invariance (LI) is the founding postulate of Einsteins 1905 theory of relativity, and therefore at the heart of all accepted theories of physics. It characterizes the invariance of the laws of physics in inertial frames under changes of velocity or orientation. This central role, and indications from unification theories hinting toward a possible LI violation, have motivated tremendous experimental efforts to test LI. A comprehensive theoretical framework to describe violations of LI has been developed over the last decade: the Lorentz violating Standard Model Extension (SME). It allows a characterization of LI violations in all fields of present day physics using a large (but finite) set of parameters which are all zero when LI is satisfied. All classical tests (e.g. Michelson-Morley or Kennedy-Thorndike experiments) can be analyzed in the SME, but it also allows the conception of new types of experiments, not thought of previously. We have carried out such a conceptually new LI test, by comparing particular atomic transitions (particular orientations of the involved nuclear spins) in the $^{133}$Cs atom using a cold atomic fountain clock. This allows us to test LI in a previously largely unexplored region of the SME parameter space, corresponding to first measurements of four proton parameters and an improvement by 11 and 12 orders of magnitude on the determination of four others. In spite of the attained accuracies, and of having extended the search into a new region of the SME, we still find no indication of LI violation.