There were several episodes that showed the huge statue foot and ankle on the island. Was the origin of said foot ever explained?
The statue was of Tawaret, the Egyptian goddess of pregnancy and fertility. It was shown in flashbacks (in LaFleur and The Incident) before the Black Rock crashed into it in the 1800s (in Ab Aeterno).
Its construction is never shown, but it was revealed in a podcast that it was built by ancient Egyptians.
There's more information on the Lost wiki.