После возвращения Флиндерсу не повезло: пришлось заняться ремонтом «Уверенности». Только в сентябре 1798 г. он и Басс были направлены губернатором в самую настоящую экспедицию для того, чтобы установить, является ли Земля Ван-Димена (Тасмания) островом или полуостровом. Командовать экспедицией должен был Флиндерс.
Губернатор выделил корабль «Норфолк» с экипажем из восьми человек, а сопровождать его должно было частное судно «Наутилус» («Кораблик») с запасом продовольствия на 12 месяцев. Плавание было удачным: мореплаватели установили островной характер Тасмании, открыли Бассов пролив и ряд крупных островов, один из которых был назван именем Флиндерса.
Вернувшись в Сидней, друзья расстались. Басс решил организовать на юге Новой Зеландии рыболовную станцию и отправился в Чили за оборудованием, но по дороге пропал без вести. А Флиндерс надеялся продолжить исследования. Казалось, он совсем обоснуется в Австралии: губернатор выделил путешественнику земельный участок площадью 300 акров в районе Бэнкстауна, здесь он получил чин лейтенанта. Однако пришлось плыть в Англию, чтобы отвести туда пришедшую в негодность «Уверенность». Вместе с ней колонию должен был покинуть и экипаж.
В августе 1800 г. корабль прибыл в Портсмут. Более шести лет Флиндерс не был на родине. И все эти годы его безропотно ждала невеста – Аннет Чеппел. Так же безропотно она наблюдала и за жестокой внутренней борьбой, которой был охвачен ее жених: ведь мизерность жалованья не позволяла Мэтью содержать семью; к тому же время от времени его неудержимо влекла Австралия. Весь долгий путь домой Флиндерс составлял карты Тасмании и побережья Нового Южного Уэльса и писал отчет о своих исследованиях. Больше всего на свете Мэтью стремился продолжить работу: через 11 дней после возвращения он направил письмо президенту Королевского общества Дж. Бэнксу с предложением организовать масштабную экспедицию для изучения побережья Австралии. Бэнкс понял важность предприятия и назначил Флиндерса руководителем экспедиции. Мэтью писал Аннет: «Теперь я или сумею сделать резкий бросок вперед, или останусь бедным лейтенантом на всю жизнь».
Вновь назначенный капитан с энтузиазмом взялся за организацию экспедиции. Он проследил за тем, чтобы на борт был взят запасной руль, оборудованы дополнительные баки для питьевой воды, запасены профилактические средства против цинги – лимонный сок, уксус и кислая капуста. Не менее тщательно капитан подошел и к отбору экипажа. В английских портах о нем сложилась добрая слава: матросы справедливо считали Флиндерса опытным навигатором и гуманным командиром. При таких качествах требовательность молодого капитана вызывала только уважение, поэтому недостатка в желающих принять участие в экспедиции не было. Флиндерс мог отбирать только самых опытных и дисциплинированных. Вторым лейтенантом экспедиции стал Сэмюэль Флиндерс, приобретший опыт в предыдущем плавании.
С помощью Бэнкса был подобран и научный состав экспедиции. В него вошли подающие большие надежды ботаник Роберт Браун, картограф Уильям Уэстолл, а также девятнадцатилетний художник Фердинанд Бауэр.
Подготовка шла полным ходом, но душа Флиндерса была неспокойна: он разрывался между страстью к исследованиям и любовью к Аннет. Это заставило его решиться на поступок, который с точки зрения пуританской морали мог считаться авантюрой, но по-человечески вполне понятен и вызывает сочувствие к обоим влюбленным.
Мэтью и Аннет тайно обвенчались. По плану Флиндерса, новобрачная должна была тайком от начальства доплыть с ним до Австралии, а во время экспедиций ждать его на берегу. Но на корабль внезапно нагрянула инспекция, которая обнаружила в каюте капитана женщину без шляпки, то есть жившую там. С пуританской точки зрения, свойственной многим англичанам, это было недопустимо. Несмотря на мольбы молодой супружеской пары, Мэтью и Аннет пришлось расстаться на долгие годы; в итоге их судьбы оказались сломленными в угоду фальшивой морали. Однако в тот момент ни один из супругов не осознавал этого; пылкий Мэтью писал молодой жене: «Теперь уже скоро я уйду из Англии, и каждый прожитый день будет приближать время моего возвращения». Ни он, ни Аннет не могли предположить, что встретиться им доведется через много лет, когда оба, особенно Флиндерс, потеряют здоровье и светлое восприятие окружающего мира.