Williams went undrafted in the 1997 NFL Draft, and signed with the Buffalo Bills as an undrafted free agent the same year. He played in just one game his rookie season. During the 1998–2000 seasons, he was a regular contributor, but did not become a regular starter until the 2001 season. In 2000, he was named to USA Today’s All-Joe Team, recognizing the NFL’s most "overlooked, ignored and hard-working" players. Williams intercepted his first career pass and returned it 20 yards for a touchdown, picking off Miami Dolphins quarterback A. J. Feeley on December 5, 2004, sealing the win for Buffalo 42-32 and breaking open a 3-point game with 1:55 left to play. Williams was named 2003 winner of the Ed Block Courage Award by his teammates. During his final four seasons with the Bills, he started in all but four games. He became a free agent after the 2004 season.
Minnesota Vikings
Prior to the 2005 season, Williams signed with the Minnesota Vikings, the 1st signing for the team in 2005 free agency and a priority signing. Following an advice by then defensive coordinatorMike Tomlin, Williams lost 15 pounds in the offseason. Williams played nose tackle in the Minnesota Vikings 4-3 defense, with teammate Kevin Williams playing the Under Tackle position. They were known collectively as the "Williams Wall" as well as the "Williams Wrecking Crew" due to their physical presence at the line of scrimmage, an attribute that helped them lead the Vikings to the best rushing defense in the league for three consecutive seasons. As a player for the Vikings, he was selected to his first Pro Bowl in 2006, and followed with consecutive selections in 2007 and 2008. He was also a second-team All-Pro selection in 2007. On December 2, 2008, Pat and teammate Kevin Williams were suspended for 4 games by the league for violating its anti-doping policy, for use of a diuretic, which can be used a masking agent for steroid use. It is believed that the diuretic was found in a weight-loss supplement that he had been taking. Williams, along with Kevin Williams, appealed the suspension to a Minnesota federal court; the judge ruled against the NFL's decision and allowed all suspended players, including Williams, to play until a further review of the case. On April 28, 2011, the Minnesota Supreme Court declined to consider Williams' appeal of the case, clearing the way for the NFL to suspend Williams. In the 2009 season, Williams made 44 tackles, 2 sacks, and 2 forced fumbles. He announced that he might retire after the season, but decided to come back for one more year in 2010. He was the oldest defensive player in the NFL. On March 2, 2011, Williams announced that he would not re-sign with the Vikings for the 2011 season. "Everything’s good. I am not coming back. Going to go finish elsewhere." He ended his NFL career playing nose tackle when he retired. On April 23, 2013, Pat Williams signed a one-day contract so that he could retire as a Minnesota Viking. Pat Williams coaches at Wossman High School as a defensive line coach.
