I'm going to assume you are using max just to get my point across.
There are a ton of plugins for max to do with landscapes, and obviously i could branch out into various other programs that i could import it into it, but there are several ways you can do it natively in max.
Make a plane with a resolution you wish (the minimum first, maybe 126x126) and then use the push/pull painting tools to sculpt the basic land mass into the plane, keeping it rough at first. After you have got the basic layout of your landmass, whack on a turbosmooth and another edit poly modifier into the stack. Now sculpt in some more finer details, flattening out parts for roads and digging ditches and other crevices for water. Keeping the modifiers seperate you can go back to any point in the creation and change it around, say for instance you wanted to make the peak of the mountain higher, it would take forever to pull them all up with 4 turbosmooths on so you will go back down to the bottom of the stack and move the lower polygon mesh. You can make displacement maps with these aswell if you ever wanted to take them into a game environment.