澳大利亚牧牛犬对澳大利亚的发展具有重大的贡献，没有它们，澳大利亚的牧牛业在发展成为重要产业时无疑会遇到巨大的困难。
在澳大利亚的早期殖民统治时期，人口主要集中在现在的悉尼等大城市区域，拥有土地的人很少，驱赶牲口到集市的距离也不远，像羊群这样的财产，少量的看护人员和犬便能使之平静并且可以控制。这些工作犬是早期的殖民者从其他国家带来的，尽管它们遭受一点当地温暖气候的痛苦，但它们在控制羊群方面的工作令人满意。
渐渐地，殖民者开始扩张。在1813年，西部出现了广阔无限的牧场，在那儿牧场主通常拥有几百甚至几千平方公里的土地，而且大多没有护栏。牛群在这种富饶的土地上变得松散，甚至已成为野牛而不易控制。
早期的牲畜贩子和牛场主所使用的最流行的犬是来自英格兰的史密斯菲尔德(Smith—field)工作犬，它属大型犬，黑色，方体，截尾。有长而粗的被毛，颈部有白色褶边。头呈楔形，耳朵呈长马鞍形，步态非常笨重。跟当时其他的工作犬一样，Smith—field犬能适应高温、艰苦的地理环境，能经过长途跋涉到达市场。早期的工作犬都有在看护家畜时乱叫和冲在前头的习惯，这对于牧羊比较好，也可以看护比较安静的牛群，但对于大牧牛场中有点野性的牛群则易导致牛群惊跑，不易控制。
不久，为了使这些野生的牛群被赶到悉尼的牲畜市场，人们需求耐力更为持久，既能安静工作又更有能力的工作犬。大约在1830年前后，一位叫泰米斯(Timmins)的牲畜贩子试着用史密斯非尔德(Smith—field)和当地一种澳洲野犬进行杂交，以便繁育出既能安静工作又更具耐力的犬。他通过这种交配方式产生的后代是一种红色的短尾犬，命名为泰米斯·贝弗斯(Timmins Biters)。与斗牛梗(smith—field)不同，该犬能安静工作但性格过于倔强，并且有严重的咬人倾向。这种杂交后代使用了一段时间后很快消失了，其他的杂交品种如粗毛柯利犬、斗牛梗的杂交犬等都不能很好地用来牧牛。
1840年，一位名叫托马斯·豪(Thomas Hall)的农场主引进了一对被毛光滑、蓝灰色的苏格兰高地柯利牧羊犬，它们可以很好地工作，但是不能吠叫和领头。托马斯用其与澳洲野犬进行杂交，繁育出种能安静工作的犬，即逐渐为人们所认识的豪西勒斯犬。这种杂交犬的颜色为红色或夹杂有黑斑的蓝灰色，其大部分为竖耳，头形似澳洲野犬，眼睛为棕色，总体还属于澳洲野犬的类型。这种犬较其他工作犬有很大的发展，逐渐成为牧牛人努力寻找的犬。
另外在昆士兰的一个农场主乔治·埃里奥特也进行了澳洲野犬与蓝色柯利犬的杂交，所培育的埃里奥特犬具有很多优秀的工作能力。牧牛人非常欣赏这种犬的工作能力，并纷纷求购幼犬。在悉尼的坎特伯雷有两兄弟，杰克与亨利买了很多这种犬并着手继续培育它们。第一步是让母犬与进口的大麦町犬进行交配，其杂交品种使杂有黑斑的蓝灰色毛发变成了红色或有蓝斑的毛色。幼犬出生时为白色，约3周后，毛的颜色开始逐渐变化。巴伽斯特 (Bengust)兄弟的目的是对该品种灌输对马的爱意，并使得这些犬易于驱使。他们培育出了这些特性，并且使这些巴伽斯特(Bengust)犬能够服从驱赶者的马及马具。但是，它们的许多工作能力丢失了。有种黑色或棕褐色的澳洲牧羊犬有很好的工作能力，于是巴伽斯特(Bengust)兄弟让其与他们的斑点犬杂交，结果培育出了一种轻巧灵活的犬。在类型上与澳洲野犬相同，但对其
进行了一些发展。其被毛厚，并有特殊斑点。世界上这种类型的犬还没有。犬身体主色为蓝色，眼睛周闱有黑色斑点，腿部、胸部与头部跟黑色或棕色澳洲牧羊犬一样有棕褐色斑点。红色的犬全身被有红色斑点，并有深红色而非黑色的斑块。
这些最接近理想状态的幼犬保留了下来，并成为今天澳大利亚牧牛犬的祖先。巴伽斯特(Bengust)犬的工作能力非常出色，保留了澳洲野犬安静工作和具有耐力的特性，并且具有大麦町犬的诚实特性。由于该犬牧牛能力非常出色，它们逐渐成为牧场主和牧牛人争相寻求的工作犬。蓝色犬证明更受欢迎，成为人们熟知的蓝色海勒斯(Hellers)犬。在昆士兰，这种犬成为大牧牛场不可缺少的得力助手。在当地，它们常称之为昆士兰海勒斯(Hellers)或昆士兰蓝色海勒斯(Hellers)犬。
与黑色或棕褐色澳洲牧羊犬杂交后，与其他品种犬的杂交均未获成功。当时的培育者致力于工作能力、类型和颜色方面的培育。1893年，罗伯特卡莱西开始培育蓝色海勒斯(Hellers)犬，并于1897年开始展览该品种犬。
卡莱西先生在1902年开始起草澳大利亚牧牛犬和澳大利亚牧羊犬的标准，他是围绕澳洲野犬类型来定位澳大利亚牧牛犬的，并且相信该品种犬天生可以适应该国家的环境条件。即使在今天，除了毛色为蓝色和红色斑点。该犬与澳洲野犬外表明显相似，尽管有许多培育者反对，但卡莱西最终使他制定的标准得以认可。他于是向澳大利亚牧牛犬俱乐部和原来的新南威尔士养犬俱乐部提交其标准并申请通过。该标准在1903年通过。
该品种逐渐以澳大利亚海勒斯的名字为人们熟知，后来定名为澳大利亚牧牛犬，这是现在整个澳大利亚认可的该品种的官方名称。然而，即使在今天还有很多人称之为蓝色海勒斯犬或昆士兰海勒斯犬。
作为一个具有多种特性的品种，澳大利亚牧牛犬于1980年5月1日在美国养犬俱乐部被登记注册，并于1980年9月1日取得工作犬协会的展示资格。后来转入1983年1月1日正式成立的牧羊犬协会。
