This paper considers cost and profit efficiency for Australian banks between 1995 and 2002. Data Envelopment Analysis (DEA) is used to construct an efficient frontier for ten banks listed on the Australian Stock Exchange. Empirical results indicate the major banks have improved their cost and profit efficiency, while the regional banks have experienced little change in cost efficiency, and a decline in profit efficiency. This result provides interesting insights into the structure of the Australian banking industry. Malmquist indices indicate technological change is the dominant source of improvements in total factor productivity over the period. An attempt is made to relate the changes in efficiency to stock returns, using a method superior to that previously adopted. Results indicate that for our sample changes in firm efficiency are reflected in stock returns.