I was previously using the query module to do this but Mark Bowen kindly pointed out the statistics module is the way to go:

{exp:stats channel="channelname"}
{total_entries}
{/exp:stats}