I think at the start there was no fee.
Some miners can put their own TX in for free when they win a block. One of them famously donated 1 BTC to Luke Dashir from a 10000 BTC UTXO and paid no fee.