Of course you do [1], and it's even very common. My cursory Google search shows that in Victory, the state with the most private ownership, 40% of all land is lease hold. Other states even more! The whole city of Canberra is leasehold. That said, it's mostly leases of Crown land, so the economic incentives are a bit different from leasing land from a private owner.
[1] http://www.actpla.act.gov.au/topics/property_purchases/lease...