Wikipedia simply says the earliest example of soap was found in Babylon, but the source provided leaves a lot to be desired.
In 'Archaeological chemistry' by Zvi Goffer it states that the earliest written and physical evidence for soap manufacture does indeed come from the 3rd Millennium BC in Babylon, but that the widespread use of soap for cleaning people (as opposed to things) doesn't occur until the Roman Empire.