W późniejszym czasie Flinders popłynął do Australii na pokładzie okrętu "The Reliance" udowadniając swoje wysokie umiejętności jako nawigator i kartograf. W 1796 rozpoczął eksplorację Australii na pokładzie maleńkiego stateczku "Tomcio Paluch" (Tom Thumb) opływając i mapując okolice Sydney. Dwa lata później opłynął dookoła Ziemię van Diemena (przemianowaną później na Tasmanię) i udowodnił, że jest ona wyspą. Cieśnina pomiędzy Australią a Tasmanią została nazwana przez niego Cieśniną Bassa (od nazwiska lekarza pokładowego George’a Bassa), a jedna w większych odkrytych wysp otrzymała później nazwę wyspy Flindersa.
W 1800 roku Flinders powrócił do Anglii gdzie wziął ślub. Wkrótce otrzymał też nowe zadanie od rządu brytyjskiego – tym razem poproszono go o opłynięcie Australii. Flinders wyruszył w drogę na pokładzie okrętu "The Investigator". 6 grudnia 1801 roku wyprawie Flindersa odsłonił się przylądek Cape Leeuwin i Flinders rozpoczął eksplorację południowego wybrzeża Australii, płynąc na wschód w kierunku Sydney. 8 kwietnia 1802 na wysokości nowo odkrytej Wyspy Kangura napotkał ekspedycję innego odkrywcy – Francuza Nicolasa Boudina. Flinders i Baudin wymienili się mapami i odkryciami, a na cześć ich spotkania Flinders nazwał zatokę w której miało ono miejsce Zatoką Spotkania (ang. Encouter Bay).