Aber leider ist bis heute noch alles erfolglos geblieben, da es hier eben so ist, wie in Deutschland, daß, wenn ein junger Mann verlangt, sich etwa 300 Mann melden. Meine Absicht ist nun mit dem nächsten Dampfschiff nach Australien zu gehen.“ Mit diesen Sätzen teilte Conrad Machens seiner Schwester Bernhardine 1878 in einem Brief aus London lakonisch seinen Entschluss zur Auswanderung mit. Eine mutige Entscheidung, die er aber nicht, so wollte er zumindest den Anschein erwecken, aus bloßer Verzweiflung fällte, sondern aus Stolz und Überzeugung: „Soll ich mich etwa als Crämer-Commis oder sogar als Hausknecht da vermiethen, wo ich bisher als Gentelmann fungirte, nein und abermals nein. Im fremden Lande ist es mir ganz einerlei, aber nicht in der Heimath. Tröste die Mutter, denn nicht in meiner Macht liegt es dieses zu ändern, sondern das Schicksal fordert dieses von mir.“ Zu diesem Zeitpunkt hatte er, das achte Kind eines Kleinbauern aus Ahrbergen bei Hildesheim, schon mehrere Jahre fern des elterlichen Hofs zugebracht: in Hannover hatte er zunächst eine kaufmännische Lehre in einem „Colonial-, Material-, Delicatess- und Fettwaaren-Geschäft“ absolviert und dann dort als Commis (Angestellter) gearbeitet. 1876 war er nach Hamburg gegangen. Es ist nicht bekannt, ob die Beendigung seiner Tätigkeit dort nur der schlechten Wirtschaftslage oder zum Teil auch seinem „ruhelosen Geist“ geschuldet war. Später bekannte er seiner Schwester, eine aus konfessionellen Gründen unerfüllbare Liebe habe ihn veranlasst, in ein „anderes fremdes Land“ zu „fliehen“. Doch vermutlich gab diese nur den letzten Ausschlag.
Am 17. September 1878 ging er in Gravesend an Bord der „SS Hankow“ der Colonial Line of Australian Packets. Für 18 Pfund hatte er ein Ticket für die dritte Klasse erworben. Die 54-tägige Seereise führte nicht durch den Suezkanal, sondern entlang der Westküste Afrikas. Unter den Passagieren waren vor allem Engländer und Schotten, was die Verständigung erschwerte. Zeitweilig ging es recht rauh zu: „Ja es war in der ersten Zeit so toll, daß, wenn sich einer dieses Leben vorher ansähe und die Absicht hätte, diese weite Reise zu machen, er gewiß lieber daheim bleiben würde, als sich unter diese Horde zu mischen“. Doch Machens wusste sich zu behaupten. Als das Schiff am 9. November im Hafen von Sydney einlief, stellte sich für ihn erneut die Existenzfrage, die auf hoher See in den Hintergrund gerückt war. Er hatte Glück: Nach knapp drei Wochen erhielt er eine Anstellung, die für seinen weiteren Werdegang schicksalhaft wurde. Im Geschäft des aus Cuxhaven stammenden Frederick Caesar Hedemann, der einen Handel zwischen Europa und der Südsee betrieb, durfte er Schreibarbeiten erledigen und „Kontrolle führen bei dem Ein- und Ausladen der Dampfer“.
Doch auf die Dauer hatte Hedemann nicht genügend Beschäftigung für den Neuankömmling. So reiste dieser im Februar 1879 per Eisenbahn in das 200 Kilometer entfernte Maitland. In der 1820 gegründeten Bergbaustadt nahm ihn der deutschstämmige Besitzer des Manu‧fakturwaren- und Herrengarderoben-Geschäfts Beckmann für acht Monate in seine Dienste. Wie bei Hedemann fand er bald engen Familienanschluss. An den Wochenenden unternahm man gemeinsame Ausflüge, und Machens lernte Reiten. Bei den Ausritten mit der Familie kam er mit Angehörigen der führenden Gesellschaftsschicht in Berührung.
