Through analyses of dental harmony in four Nilotic languages, this paper argues both for contrastive representations and for a stratal version of Optimality Theory. Dholuo, Päri, Shilluk and Anywa all have dental harmony patterns which bar the co-occurrence of dental and alveolar segments. Details of the dental harmony patterning vary between languages and are tied to contrasts in the inventory. In Anywa, harmony is non-structure-preserving and an allophonic dental nasal surfaces in harmonic forms. This pattern can be analyzed in a stratal model of OT but leads to a ranking paradox if only a single level of evaluation is used. Further support for a stratal analysis can be found in the interaction between harmony and consonant mutation processes in the four languages. In Dholuo, harmony applies at the stem level and consonant mutation results in disharmonic surface forms in morphologically complex words. In Anywa, harmony applies later, at the word level, and words formed through consonant mutation must obey the dental harmony restrictions.