At "UFC 10" in Birmingham, Alabama on July 12, 1996, Frye returned to tournament format. He defeated Mark Hall by stoppage, slamming the Moo Yea Do specialist and working his side with body punches until the stoppage, and then eliminated Brian Johnston, again leading the action to the mat and landing elbows to the head. However, at the finals of the event, Frye faced his toughest challenge yet, Mark Coleman, who was considered the "godfather" of the ground and pound strategy Frye often followed. Coleman, a more decorated wrestling champion than Frye himself, kept the top position through the match and landed multiple strikes to the face. Frye capitalized on a failed neck crank attempt to get standing and try to outmatch Coleman there, but he was taken down again, and a late takedown attempt of his own also failed, with Coleman reversing and threatening with an overhead throw before returning to his routine. At the end, after Coleman secured side mount and dropped punches and headbutts onto Frye's face, the referee stopped the action, handing Frye his first loss in seven fights.