Location-based services (LBS) are defined as those applications that combine the location of a mobile device associated with a given entity (individual or object) together with contextual information to offer a value-added service. LBS solutions are being deployed globally, and in some markets like Australia, without appropriate regulatory provisions in place. Recent debates in Australia have addressed the need to bridge the gap between technological developments and legal/regulatory provisions. This requires an assessment of the regulatory environment within a given social context such as Australia. The core components of such an investigation include: (a) composing a conceptual framework for analysing regulation of technologies such as LBS, one that is sensitive to public policy themes and challenges, and (b) applying this conceptual framework to the Australian setting in order to sketch and define the components of the present framework, and identify areas for improvement through a process of validation. This paper addresses these aims, demonstrating how the current regulatory framework in Australia is bound by legislation with respect to privacy, telecommunications, surveillance, and national security (that is, anti-terrorism), in addition to a set of industry guidelines for location-service providers (LSPs). The existing Australian framework, however, is lacking in its coverage and treatment of LBS and location data, and does not adequately address the themes and challenges in the defined conceptual framework.