Mayfield was born in Coos Bay, Oregon and grew up in Halstead, Kansas. He served in the United States Army Reserve from 1985 to 1989, and then as an officer in the Army in Bitburg, Germany from 1992 to 1994. He met his wife Mona, an Egyptian national and the daughter of a college professor, on a blind date in Olympia, Washington in 1986, and converted to Islam shortly afterwards. They have lived in Beaverton, Oregon off and on since 1989. Although he was a regular worshiper at a Beaverton mosque prior to his arrest, his colleagues were unaware of his religious beliefs. The imam of the mosque has described Mayfield as "very patriotic".
In 2003 he offered legal aid to Jeffrey Leon Battle, one of the Portland Seven, a group of people convicted of trying to travel to Afghanistan to help the Taliban.
Fingerprints on a bag containing detonating devices, found by Spanish authorities following the Madrid commuter train bombings, were initially identified by the FBI as belonging to Mayfield ("100% verified"). According to the court documents in judge Ann Aiken's decision, this information was largely "fabricated and concocted by the FBI and DOJ". When the FBI finally sent Mayfield's fingerprints to the Spanish authorities, they contested the matching of the fingerprints from Brandon Mayfield to the ones associated with the Madrid bombing. Further, the Spanish authorities informed the FBI they had other suspects in the case, Moroccan immigrants not linked to anyone in the USA. The FBI completely disregarded all of the information from the Spanish authorities, and proceeded to spy on Mayfield and his family further.