Madurese, a Western Malayo-Polynesian language spoken on the Indonesian island of Madura, has been described as having a three-way voicing contrast (i.e. voiced, voiceless unaspirated and voiceless aspirated) in its stops. However, the fact that the VOT values for voiceless unaspirated and aspirated stops are not large and they are also followed by vowels with different height raises a question if Madurese only contrasts voiced and voiceless stops phonologically instead. The goal of this paper is to establish the phonological status of the voicing contrast in Madurese stops, arguing that Madurese can be better described as a language with a three-way contrast. For this purpose, we provide phonological evidence that includes consonant-vowel interactions, vowel harmony processes and some morphophonemic processes involving vowel height alternations. All of this evidence is also used to substantiate the proposal that consonants trigger vowel height alternation rather than vowels trigger consonant allophony.