I assume they began building the walls as soon as the Titans first appeared, and let the other communities of the world die while they furiously worked on their wall. It may have started out small, since most of the Titans are only a little larger than a two-story house. Over time, they built it larger and larger and larger. They were quite confident that there would never be any 50 meter Titans.
They may have built the inner wall first, started building more walls, eradicated Titans within, and then moved out another layer.
Just because the people are complacent and shitty fighters ready to piss themselves now, doesn't mean they always were. They may have been quite a bit more desperate, and willing to sacrifice a lot more lives for the greater good.
The people seem to look down on the Recon/Scouting Legion these days, but an offensive unit was probably much more important before.
edit:
@Kraco: It's hard to judge their level of technology from the first episode. While Eren and Mikasa are picking up sticks for firewood and live in a medieval looking house, the walls do have artillery canons on them, on railroad tracks no less.
Not to mention the wire grappling machines. I wish we had those.