1. Expedition: Rund um Perth

1846 unternahm er mit seinen beiden Brüdern F. T. Gregory und H. C. Gregory seine erste Expedition. Mit vier Pferden und Proviant für sieben Wochen verließen sie am 7. August 1846 die etwa 100 km nordöstlich von Perth gelegene T. N. Yule’s Station. Als sie nach 47 Tagen zurückkehrten, hatten sie einen Großteil der Region nördlich von Perth erkundet und dabei 1.534 km zurückgelegt.

2. Expedition: Westküste / Murchison River

Zwei Jahre später leitete Gregory eine Expedition, um den Lauf des Gascoyne River zu erforschen und zugleich neue Weidegebiete zu finden. Die Gruppe brach am 2. September 1848 auf und überquerte am 25. September den Murchison River, doch das Land war sehr trocken, und es war sehr schwer, ausreichend Wasser für die Pferde zu beschaffen. Anfang Oktober beschloss Gregory, nach Süden umzukehren. Am 6. Oktober, als sie erneut am Murchison River angekommen waren, entschied er, hier mit den Pferden Rast zu machen. Am 12. November kehrte die Expeditionsgruppe nach Perth zurück, nachdem sie gutes Weideland gefunden hatte. Trotz Wassermangels legten die Expeditionsteilnehmer innerhalb von zehn Wochen 2.414 km zurück.

3. Expedition: Nordaustralien / Victoria River

1854 wurde Gregory gebeten, eine Expedition ins Landesinnere zu leiten. Gregory bestimmte seinen Bruder H. C. Gregory zum zweiten Expeditionsleiter; im Team befand sich auch der Botaniker Baron Ferdinand von Mueller. Zusammen waren sie 18 Männer, 50 Pferde und 200 Schafe. Die Gruppe verließ am 12. August 1855 die Moreton Bay bei Brisbane mit dem Schiff in nördliche Gewässer. Sie erreichten am 1. September Port Essington. Am nächsten Tag lief das Schiff auf ein Riff auf, und es war zehn Tage lang nicht möglich, das Schiff vom Fleck zu bewegen. Dann ging es weiter nach Pearce Point am Joseph Bonaparte Gulf (Timorsee), nördlich des Ästuars eines Flusses, den Gregory später Victoria River nannte. Am Monatsende teilte sich die Gruppe auf: Während Gregory den einen Teil über die Weideländer führte, fuhren die anderen mit einem Schoner den Victoria River hinauf. Erst am 20. Oktober vereinte sich die Gruppe wieder und errichtete ein Camp ca. 20 km westlich des heutigen Timber Creek. Während die Mannschaft bis Juli 1956 im Basis-Camp verblieb, unternahm Gregory mit wenigen Begleitern 8 Monate lang Expeditionen ins Landesinnere. Sie fuhren in der Regenzeit den Victoria River flussaufwärts, erreichten den Sturt Creek, der nur im Sommer Wasser führt, und folgten diesem bis an den Rand der Tanami Desert. Einen Hinweis auf das Basis-Camp, zu dem Gregorys Kernteam zur Trockenzeit 1856 zurückkehrte, finden wir am so genannten Gregory’s Tree, einem Boab, in den Gregory das Datum „2. Juli 1856“ ritzte sowie den Hinweis auf einen Brief, den er hinterlegt habe (für potenzielle Suchtrupps, falls das Team verloren gegangen wäre). Nach Verlassen des Basis-Camps schlugen sich die Expeditionsmitglieder dann über sechs Monate parallel zur Küste – verschiedene Flüsse entdeckend und nutzend – durch das Landesinnere nach Südosten. Am 16. Dezember 1856 erreichten sie ihren Ausgangsort Brisbane, nachdem sie große Teile des Landes vermessen hatten. In 16 Monaten hatten sie eine Strecke von 3219 km übers Meer und 8047 km über Land zurückgelegt.

4. Expedition: Südosten: Suche nach Ludwig Leichhardt

Im September des Jahres 1857 wurde er von der Regierung von New South Wales beauftragt, nach Spuren des auf einer früheren Expedition verschwundenen Entdeckers Ludwig Leichhardt zu suchen. Eine neunköpfige Gruppe wurde gebildet, mit Gregory und dessen Bruder C. F. Gregory als Führer. Am 24. März 1858 verließ die Expedition Juandah. Am 21. April entdeckten sie einen Baum, in den ein L geritzt war. Die Gruppe folgte dann dem Barcoo River bis zu dessen Zusammenfluss mit dem Thomson River. Am 15. Mai war das Land so trocken, dass Gregory beschloss, zum Schutz der Pferde nach Süden zu ziehen. Danach folgten sie dem Cooper Creek, bis sie am 14. Juni den Strzelecki Creek erreichten. Sie setzten ihre Route nach Süden fort, bis Gregory am 26. Juni entschied, Adelaide anzusteuern, das sie Ende Juli erreichten.

Das Expeditionstagebuch von Gregory wurde 1884 veröffentlicht.