Possibly not. The IMEI of the phone is linked to the network.
If it's Telstra you may be able to unlink it at telstra.com/unlock - at minimum it will tell you how to get the IMEI which you will need.
If it's out of contract the provider should be able to unlock it easily. If it's an iPhone 3 it should be well out of contract.
Optus were quite cooperative when unlocking mine.