Om zijn carrière nieuw leven in te blazen maakte Martin Max in de zomer van 1995 de overstap van Borussia Mönchengladbach naar het uit [[Gelsenkirchen]] afkomstige [[FC Schalke 04|Schalke 04]]. Bij de club uit het Ruhrgebied raakte Martin Max weer op dreef. Zijn competitiedebuut voor Schalke maakte hij in een wedstrijd tegen [[1. FC Köln]], die met 1-0 gewonnen werd door een doelpunt van de Nederlander [[Youri Mulder]]. Max scoorde zelf voor het eerst voor de club tegen Hansa Rostock. Dat seizoen zou hij nog tien keer scoren. Rond dat niveau bleef de Duitser spelen voor Schalke gedurende de rest van zijn tijd bij Schalke. Ook in de [[UEFA Cup]] van het seizoen 1996/199797 was Max belangrijk. Hij scoorde drie doelpunten en speelde ook mee in beide finalewedstrijden, waarvoor Schalke zich had geplaatst. Nadat Schalke in Gelsenkirchen met 1-0 had gewonnen, werd er in Milaan met 1-0 verloren. Daardoor kwam het aan op strafschoppen[[strafschop]]pen. Martin Max nam de derde voor Schalke 04 en scoorde deze. Doordat de Duitsers geen van hun penalty's misten, terwijl Internazionale tot tweemaal toe niet wist raak te schieten, won Schalke 04 dat seizoen de UEFA Cup. Het seizoen 1998/199999 zou het laatste seizoenzijn dat Martin Max bij Schalke 04 zou spelen. Daarna maakte hij de overstap naar een andere Duitse club. Voor Schalke speelde hij in totaal 109 wedstrijden. 33 keer wist hij daarbij het doel te treffen.
