Facebook permanently stores all status updates you ever wrote. Even if you don't see them anywhere, they're still there. The only way to delete them is to open them in the browser manually, one-by-one, and click "Remove Post" for each of them.

The Graph API only allows you to delete status updates that were originally created by your own application. So it doesn't help here.

To make deleting old status updates a bit more automated, I combined two tools:

Using this Python script, you can generate a Selenium Test Case that loops through all your old status updates (older than 30 days by default) and deletes them by clicking the relevant buttons on the page:

You can run it like this:

./fbdel.py > fbdel.html

The script will open a web browser and ask you to authenticate the fbconsole application. Then it takes a while and generates the fbdel.html file, printing out the status updates to stderr.

Once the script is finished, you can open fbdel.html in Selenium. You will see a long list of actions and you can click them individually if you just want to see what the script is doing. To run them all, click the "Play entire test suite" button. Please understand you will do this at your own risk.

It's very likely that the script will timeout and break at some point. You can always run fbdel.py again to generate a new Test Case with the remaining status updates. Also I am not certain whether FQL allows you to access you entire status update history. For me, it seemed to return about 2 years of them and I'm still trying to check whether there are older ones lurking out there somewhere.

Finally, remember that this will only delete status updates. If you want to clean up your entire history, you need to do the same for your shared links, likes, checkins, photos, comments, application-specific updates (e.g. Twitter) and so on.