The protections include gender identity and gender expression said Phillip Keene, a company spokesperson.

Keene did not confirm when the new policy went into effect, only that the change was made "several weeks ago."

News of the new policy has not been widely publicized.

Sexual orientation protections are already a part of the company's "Discrimination and Harassment Prevention Policy."

"We've had a strong anti-discrimination policy for a long time," said Keene.

Wal-Mart scored relatively poorly on the Human Rights Campaign's annual Corporate Equality Index, which ranks major companies on their LGBT policies and practices. Wal-Mart received a 40 percent ranking out of 100, for a failure to amend its anti-discrimination policy to include gender protections last year.

Keene said that the addition of gender protections in the policy was precipitated by a standard review of the policy and not by complaints.