Mathew Hayman si trasferisce in Olanda nel 1997, all'età di 19 anni. Disputa tre stagioni (1997-98-99) come dilettante prima di passare professionista nel 2000. Mathew è australiano ma corre con licenza olandese e nel 1999 è il primo straniero a vincere la corsa valida per il Campionato d'Olanda su strada dilettanti. A fine anno è primo nella classifica UCI categoria Under 23 e firma un contratto da professionista per due anni con la Rabobank. Nella prima stagione da pro non ottiene risultati di rilievo e solo a tratti si intravedono le sue potenzialità, poi un infortunio pone termine in anticipo alla stagione.
Il 2001 lo inizia alla grande vincendo a febbraio una prova del Challenge Maiorca e la classifica finale, ma nel resto della stagione non seguono conferme. La Rabobank gli concede fiducia e gli rinnova il contratto anche per la stagione successiva. Dal 2002 al 2004 corre quindi ancora in Olanda per la Rabobank, ottiene discreti piazzamenti ma alla fine della stagione 2004 non ha ancora ritrovato lo spunto vincente.