I've re-written in a summarized flowchart form what I've previously mentioned (since that seems to be too much for many of us to digest) on whether or not you need to reveal your former name when applying for jobs (if asked; if not don't mention anything unless they want to check a record that's under that name, and if they ask only if specific information is under another name answer appropriately), applicable to the U.S. only.

1. Is this a "high security" job (such as one with the government and/or requires a security clearance, law enforcement, etc.) where they'll do an investigation that in general legally can't be done by an employer? If yes, go to Step 7. If no, go to Step 2.
2. Do you have any criminal history on record under your former name? If yes, go to Step 7. If no, go to Step 3.
3. If the company wants to pull up your credit history (legally you should be given notification if they do), are any of the entries under your former name? If yes, go to Step 7. If no or they're not going to pull it, go to Step 4.
4. Do all of your references know you by your new name? If yes, go to Step 5. If no, go to Step 8.
5. Is all of your work and educational history (as well as any relevant certifications/licenses) under your new name (either because you changed your name before your first job or attended the institution, or all such places have updated your records)? If yes, go to Step 10. If no, go to Step 6.
6. Is any of the work or educational history under your former name something they'd likely check? (Things they'd unlikely check would be for example decades-old work history or secondary school records once you've graduated from college.) If yes, go to Step 8. If no, go to Step 9.
7. You must disclose that name, or you could run into trouble legally by concealing important information.
8. You'll probably have to eventually disclose that name (or else you may get a work/school/reference check that bounces back because they don't know or can't locate you by your new name), but you could put down something like "will discuss" or "available upon request" if you want to avoid mentioning it when making your first impression.
9. As with the Step 8 scenario you could mention something similar, but this time first mention if asked that you had a name change so many years ago and that chances are the stuff they'd want to check wouldn't be under that name.
10. You probably don't need to even bring up that your name was changed, but if you want to be safe you could put down that no relevant records are under any other name (and they'd generally assume you had a pre-adulthood name change).

This could probably also apply to applications for credit, but start with Step 2 (or Step 3 if there won't be any criminal history checks) and if you end up at Step 5 go to Step 10. Since most employers these days will want to know about your criminal background to some extent I include Step 2 unconditionally.

Sources:
Guidelines on what's legal and what's not for employers to ask, and ways for an applicant to handle dicey questions. A question made by someone who was adopted on a forum on whether or not a name change made as a child is relevant when applying for jobs (which except for the #1 scenario in this post where they trace you back to birth is usually "no"). It should also be noted that having legally changed your name is not the only way that one of these steps may be triggered; if you committed a crime under an alias, or if you're known to references by or have credit under a nickname or other name, they'd need to know that in order for the checks to go through properly (and conversely a legal name change that does not trigger one of these steps, such as the aforementioned adoption in non-#1 cases, is typically not relevant). Since I'm not a professional on this subject matter, don't take this advice as if I was (it's based on research from the sources I mentioned).

ETA: Added certifications/licenses in Step 5.

I just bought a new car, applied under my new name and had no issues. I legally changed my name like 4-5 years ago and had all my bank accounts/credit cards etc changed. I asked about reporting my name change to the credit bureaus, they informed my they don't accept these and it will automatically "update" under my new name. My old name at this point likely has a zero credit rating from non-use.  It is NOT illegal to have credit established in your new name nor are you required to disclose a name change. One of the things you swear when changing your name is that you aren't doing this to dodge credit/debt problems. The other thing too and I ran into this, if there is a legal document in your old name you have to sign, notarize or otherwise prove it is you, all you need is your present ID and the court name change document showing the paper trail.

As far as job applications? I guess it depends on the job but I'm not planning on ever disclosing my old name to anyone.

I think this also varies from country to country. In Australia I cannot be legally discriminated on my name. I have had a legal name change and that is that. I have no need to ever reveal my former name. As Stephe said I have a copy of the legal document linking my old name a new name and if I need to provide proof that something bought or decided under my previous name is my property etc I just have to show that. For example I have a power of attorney under my old name which is still legal and valid under my new name on demonstrating the link.

I have changed my name on all my documents, licences etc. I told my work place that I had changed my name and they immediately changed my security cards, pay office and human resource records to my new name. No questions. They just wanted a copy of the document as proof.

What if you have a prostitution record under BOTH names? 

Quote from: Aryana_V on November 19, 2012, 11:02:48 PM
What if you have a prostitution record under BOTH names? 

Get a third and change professions?

Quote from: Cindy James on November 20, 2012, 12:08:48 AM
Get a third and change professions?

t
I gave that "profession" up long ago, but I guess it's the wreckage of the past coming back to bite me. It's funny you mention third name change because I did consider  that, but I suppose people would think I wasn't serious if I kept  switching names(and i like my name and it means a lot to me)... but OHH the thought is there

I had to give my previous name when I applied for my alcohol licence last year,there was a box to tick for transgender people.It's probably different for other countrys

Quote from: big kim on November 21, 2012, 05:36:40 AM
I had to give my previous name when I applied for my alcohol licence last year,there was a box to tick for transgender people.It's probably different for other countrys

What country are you in? (Since you used the "licence" spelling I assume it's not the U.S.)

ETA: Most of us don't have a problem with explaining our past if necessary when we're applying for something like a passport or government-issued license (as long as the issued document itself doesn't indicate your former name and/or gender); in that case do mention any past names (within the terms of the question) if asked unless you know in your situation it isn't necessary (e.g. if you're name was changed as a child you can ask to see if they still need to know it or not). What I'm talking about is when applying for a job, loan, etc. where the other party knowing that you're TS may lead to discrimination; in that case it's generally assumed that they only need to know (and in some cases are only supposed to ask) what other names are necessary to properly check your background. In such cases they thus usually do not need to know about childhood name changes, but if they need to contact a reference or check records that are under your former name they would then need to know or you may face problems with trying to conceal your past records (hence the "flowchart" I made to determine if you need to disclose your former name in your case or not). These guidelines with dealing with former names, which apply in many U.S. States (but surprisingly not California where an employer can legally can ask for any past names as long as they don't ask why it was changed, which obviously doesn't work for TSs), originated because of immigrants who changed their names to assimilate being unnecessarily asked about their national origin (and minimizing inquiries to what's necessary).

England they needed a criminal record check so I could get an alcohol licence for the guest house and the owners could get a premises licence.Very complicated and expensive

Quote from: big kim on November 21, 2012, 12:10:19 PM
England they needed a criminal record check so I could get an alcohol licence for the guest house and the owners could get a premises licence.Very complicated and expensive

I understand that if you need a criminal records check in the UK they have a special procedure for transgender people so they don't have to out themselves to an employer or the like. Over there they generally have more special procedures for TSs than in the U.S., while in the latter you have a bit more "off the top" protection that would apply to anyone whose name was changed (such as the guidelines I mentioned on whether they need to know your former name or not) but fewer TS-dedicated procedures (which means that if a record exists under your old name that they want to check you'll probably have to out yourself).