ORCHARD PARK, N.Y. -- The Buffalo Bills rode their reinvigorated rushing attack to their first victory of the season.

LeSean McCoy ran for 110 yards and two touchdowns, Tyrod Taylor scrambled for 78 yards and a touchdown, and the Buffalo Bills defeated the Arizona Cardinals 33-18 on Sunday at New Era Field.

Playing without top wideout Sammy Watkins (foot) and left tackle Cordy Glenn (ankle), the Bills (1-2) rushed for 209 yards, the most by any team so far this season. The Bills led the NFL in rushing last season, but totaled just 151 yards in their first two losses.

"This is what we do," guard Richie Incognito said. "This is what we are built for. This is the way we were assembled in the offseason and it's nice to see everything come to fruition."

Buffalo's ground game found its footing after coach Rex Ryan fired offensive coordinator Greg Roman and promoted running backs coach Anthony Lynn to replace Roman.

"I don't think anybody needed a win more than we did," Ryan said. "We are going to enjoy the fact that we knew what everybody thought of our football team and we knew we were a better team than that."

The Bills' defense, which had also struggled through the first two weeks, bottled up the Cardinals for most of the game, forcing five straight three-and-outs at the start and intercepting Carson Palmer on each of Arizona's last four possessions.

"The defense did a great job," center Eric Wood said. "That allows us to wear down the defense. It was kind of the opposite of what happened to us in the first games. "They were going three-and-out as opposed to us going three-and-out early, so that was awesome."

David Johnson rushed for 83 yards and two touchdowns for the Cardinals (1-2), who played their first road game of the season. Palmer completed 26 of 50 passes for 264 yards. It was the fifth time in his career Palmer threw four interceptions, and the first time he did so without throwing a touchdown pass.

"Obviously, disappointed in the way we played. Disappointed in myself and the way I played," Palmer said. "But there's a lot of football left. There's 13 games left."

Taylor completed 14 of 25 passes for 119 yards and an interception.

"They were gashing us, so they didn't really have to pass the ball if they didn't want to," Cardinals safety Tony Jefferson said.

Johnson scored his second touchdown on a 22-yard run toward the end of the third quarter, but Palmer's two-point pass failed, leaving the Bills in front 30-13.

Chandler Catanzaro then made a 60-yard field goal to bring the Cardinals within two touchdowns with 10:36 left in the fourth quarter. Catanzaro's kick set a stadium record but came up one yard short of Jay Feely's team record set in a loss to the Bills on Oct. 14, 2012.

Dan Carpenter's 45-yard field goal gave the Bills a 17-point lead with less than five minutes remaining.

The Cardinals regained some life with 3:04 left to play when Corey Peters tackled McCoy in the end zone for a safety following Corey Graham's diving interception of Palmer at the 1-yard line. But Stephon Gilmore made his second interception of the game in the end zone to thwart Arizona's comeback. Corey White also intercepted Palmer late.

The Bills built their lead to 30-7 by taking advantage of the Cardinals' first turnover of the season. Arizona holder Drew Butler couldn't handle a high snap on a third quarter field-goal attempt and Aaron Williams returned the fumble 53 yards for a touchdown.

Taylor high-stepped it into the end zone at the end of a 20-yard touchdown run that gave the Bills a 23-7 lead early in the third quarter.

The Cardinals failed to score in the first quarter for the third straight game but found their offensive rhythm in the second.

"We talked all week about getting off to a fast start and that's the slowest one we've had in four years, offensively," Arizona coach Bruce Arians said.

After netting no yards on their first five possessions, the Cardinals engineered an 84-yard drive that spanned 9:34 and cut the lead to 17-7 on Johnson's 4-yard run with 51 seconds left in the half. The drive was extended twice by Buffalo penalties on third down, one for unnecessary roughness on linebacker Jerry Hughes for ripping off Palmer's helmet, and one for defensive holding on linebacker Lorenzo Alexander.

McCoy scored on a 24-yard run off tackle late in the first quarter and a 5-yard outside run to put the Bills ahead 17-0 five minutes into the second quarter.

Taylor set a Bills' record for longest run by a quarterback with a 49-yard gain in the first quarter that led to a 19-yard Carpenter field goal.

NOTES: Starting RG Evan Mathis (foot/toe), DT Frostee Rucker (knee), and first-round pick Robert Nkemdiche (ankle) did not play for the Cardinals. ... The Bills were also without CB Ronald Darby (hamstring). ... LB Chandler Jones became the third Cardinals player to record a sack in each of the season's first three games, joining Bertrand Berry (2008) and Curtis Greer (1985). ... Steve Christie held the previous record for the longest field goal at what was then known as Rich Stadium, a 59-yarder against the Dolphins on Sept. 26, 1993.