At age 18, Beach won a small role in the miniseries Lost in the Barrens, based on the Farley Mowat novel. In the following years, he continued to work in local theatre and guest-starred on television shows like Walker, Texas Ranger and Touched by an Angel. Shortly afterwards, Beach was cast as a regular on the television shows North of 60 and The Rez.
After his performance in Dance Me Outside he starred in Smoke Signals, which was nominated for the Grand Jury Prize at the Sundance Film Festival. He took a small role in Disney's Mystery, Alaska in 1999 and in 2000 accepted a role in the thriller, The Last Stop. Beach then appeared in The Art of Woo and the 2001 hit Joe Dirt as Kicking Wing, a Native American fireworks salesman.
In 2002, Windtalkers, starring Beach, came out in theatres. To prepare for this role, Beach spent six months learning the Navajo language. He was also able to use this skill in his next project, Skinwalkers, directed by Chris Eyre, who gave him his breakout role in Smoke Signals.
Between large-scale projects, Beach made small television appearances on such shows as JAG and Third Watch. Also, in 2003, he returned to the character that he first portrayed in Skinwalkers in the movie Coyote Waits. He also made a guest appearance in the hit show The Dead Zone as a Native shaman (in the episode "Shaman").
In 2006, Beach portrayed Ira Hayes in Clint Eastwood's feature film Flags of Our Fathers. During the filming of this movie, both Beach's grandmother and his best friend died. Beach commented, "And if you add those up, there's a lot of emotion. When you're doing a movie, when you let go emotionally, there's nothing to grab onto," he said about the deaths. About playing the part, Beach said, "For me, playing Ira was a meaningful relationship. I would call it – trying to find out how he was, or how he thought and felt". The movie won two Academy Award nominations and Beach was nominated for multiple Best Supporting Actor honors.
In 2007, Beach starred in HBO Films' adaptation of Dee Brown's history, Bury My Heart at Wounded Knee. In the film, Beach portrays the Sioux advocate, author and medical doctor Charles Eastman (Dakota name, Ohiyesa) and his changing understanding of Aboriginal-US relations during the period leading up to the Wounded Knee Massacre.
In addition to starring in the Canadian television series Moose TV, Beach is executive-producing and starring in the movie Older Than America, the independent feature filmed in Cloquet, Minnesota mostly on the Fond du Lac Ojibwe reservation. He also joined the cast of Law & Order: Special Victims Unit as Detective Chester Lake for the show's ninth season after guest-starring in season eight. However, in April 2008, TV Guide announced that he would not return for the show's tenth season.
In 2006, Beach unsuccessfully attempted to run for the leadership of his Lake Manitoba First Nation, but has stated he will try again during the next election.
Starting in 2009, Beach plays a supporting role on the HBO series, Big Love as a manager in an Indian casino with Bill Henrickson (Bill Paxton).