Electronic government (e-government) breaks down the barrier of distance and time, and offers the potential for government to better deliver its contents and services, and interact with citizens and businesses. Australia has been recognized as one of e-government leaders internationally. All the three levels (federal, state and local) of Australian government organizations have increasingly embraced e-government. With few years of e-government practices in Australia, it is critical to evaluate the current applications and explore more effective strategies for the next phase of e-government. This study aims to identify what factors affect the effectiveness of Australian e-government online services. In the study, a research model is proposed and data collections are completed based on two questionnaire-based surveys from internal and external users of Australian e-government Web sites respectively. Furthermore, data analyses are conducted to test proposed hypotheses. The findings show that Web presence quality and information quality influence effectiveness of e-government online services more than system quality from user perspectives. Several recommendations and future trends are also presented in the chapter.