The objective of this paper is to measure health literacy in a representative sample of the Australian general population using three health literacy tools; to consider the congruency of results; and to determine whether these assessments were associated with socio-demographic characteristics. Face-to-face interviews were conducted in a stratified random sample of the adult Victorian population identified from the 2004 Australian Government Electoral Roll. Participants were invited to participate by mail and follow-up telephone call. Health literacy was measured using the Rapid Estimate of Adult Literacy in Medicine (REALM), Test of Functional Health Literacy in Adults (TOFHLA) and Newest Vital Sign (NVS). Of 1680 people invited to participate, 89 (5.3%) were ineligible, 750 (44.6%) were not contactable by phone, 531 (32%) refused and 310 (response rate 310/1591, 19.5%) agreed to participate. Compared with the general population, participants were slightly older, better educated and had a higher annual income. The proportion of participants with less than adequate health literacy levels varied: 26.0% (80/308) for the NVS, 10.6% (51 33/310) for the REALM and 6.8% (21/309) for the TOFHLA. A varying but significant proportion of the general population was found to have limited health literacy. The health literacy measures we used, while moderately correlated, appear to measure different but related constructs and use different cut offs to indicate poor health literacy.