A lot of that answer is going to depend on what else you have on your credit report - if this is the only thing then I would be tempted to pay off the majority of it (to minimize interest) but keep a very small balance that you can make on time payments for each month.
You could then take whatever you don't pay off (say you pay off $4000) you would have $1000 and use it to open a secured card - let less than 9% balance report and always PIF before the cut off date and then once your score goes up apply for an additional unsecured card.
Of course that goes out the window if you already have an established history, other cards/items reporting, a good score and you don't carry balances 
So really, I am saying, it depends.