Debt on Report Help

[NapoliJ10]

I am in need of advice / assistance on my situation.  I'm new to tracking my credit and new to the world of understanding credit.

I've recently taken interest in my credit because my auto loan has been fulfilled and I am in the market for some new credit lines.  Other than my auto loan, the only other information showing on my report is a supposed debt I didn't know I had.  The original creditor is listed as "AT T."  I have since contacted AT&T and have been informed by multiple people in different departments that I do not have any outstanding balance and nothing showing as being sent to a collection agency.  I am not receiving any communication from the collection agency about this debt; the only reason I am aware of it is because I checked my credit report.

I don't know what steps I should take.

Should I call them and ask them for any information regarding proof of the debt?

Should I send a letter requesting such information?

Should I dispute the debt through the credit bureau?

Is there something else I can / should do?

Before I open up a new line of credit I would love to take care of this matter; I just have no idea what to do.

Thanks to any and to all in advance for help!

[Whitneyy]

Yes, you need to send a DV. 

[dursty87]

---

@Whitneyy wrote:

Yes, you need to send a DV. 

---

+1.  This should be done in writing and sent CMRRR.

[NapoliJ10]

Thanks very much for the tips!  I sent off a debt validation letter and they responded within a few days.  I am putting together a Pay For Delete letter now and will be sending that off in the next few days.  I do have a new question regarding this process.  They currently have the collection account removed from my credit report.  Prior to that removal I had applied to Bank of America and Capital One for a secured credit card.  I was approved by both and have since activated the Bank of America card (hoping that it unsecures 12 months from now).  My question is, now that the collection is not currently on my credit report and my score has gone up nearly 100 points, should I apply for an unsecured credit card, or would that be an unwise decision?

Either way, I have the single secured card for now and plan on activating the Capital One card soon, but it would be nice to not have two annual fee cards to deal with if I can have a single secured and start out now with an unsecured as well.

Thanks in advanced for any assistance!