Spoilers from the manga.
After the king's sanctum incident (ch50~65)
(when Rod Reiss tried to make Historia eat Eren),
it is disclosed that
The First King used his Coordinate power (control over titans) to force those titans to use their hardening power to shape up the walls, then used his Memory power to wipe the memories from the pre-wall era from humanity.
Why did he
leave hibernatingtitans inside the walls
is unknown.
he also created the Wallist Church to help him oversee the walls safety.