Grissom played baseball at Florida A&M University, and in 1988, the Montreal Expos selected him with the 76th overall pick in the June draft, as part of that draft's third round. He had been considered a prospect as both a pitcher and an outfielder, but the Expos decided to have him abandon the mound and work solely as a position player. He made his professional debut with the Jamestown Expos of the New York-Penn League that fall and advanced quickly through the system, first appearing in the majors on August 22, 1989. He showed steady improvement for the next few seasons, gradually developing into a star as Montreal's leadoff hitter and center fielder. He led the National League in stolen bases in 1991 and 1992, was a member of the NL All-Star team in 1993 and 1994, and won four consecutive Gold Gloves, the first coming in 1993.
The Expos enjoyed success on the field, but a strike ended the 1994 season before the playoffs, and after baseball resumed the team was forced to trade many of their stars for financial reasons. In April 1995, the Expos traded Grissom to the Atlanta Braves, in exchange for pitcher Esteban Yan and outfielders Roberto Kelly and Tony Tarasco. The Braves were just beginning a run of dominance in the NL East, and in his first season in Atlanta, they won the World Series with Marquis (the only player on that Atlanta Braves team who actually was born and raised in Atlanta) securing the final out by catching a fly ball by Carlos Baerga. They returned to the fall classic the next season, but failed to defend their title against the New York Yankees.
Teams' financial motivations continued to affect the course of Grissom's career, and in March 1997, he was involved in a blockbuster trade with the Cleveland Indians. Hoping to save money that had been committed to long-term contracts, Atlanta traded Grissom and two-time All-Star David Justice to the Indians, receiving in return three-time All-Star Kenny Lofton and setup man Alan Embree. The deal worked out well for Cleveland, as the team went all the way to the World Series, ultimately losing to the Florida Marlins in seven games. Grissom performed exceptionally well in that postseason, winning the MVP award in the ALCS, and completing a 15 game World Series consecutive game hitting streak spanning 3 World Series, the 2nd longest of all time next to Hank Bauer of the New York Yankees.
That offseason, however, the Indians re-signed Lofton as a free agent, subsequently trading Grissom and pitcher Jeff Juden to the Milwaukee Brewers for pitchers Ben McDonald, Ron Villone, and Mike Fetters. Grissom's production declined as he spent three seasons with the struggling club, and a trade in the spring of 2001 made him a Los Angeles Dodger, sending Devon White to the Brewers in return. Grissom continued to struggle that year, but he enjoyed a strong bounce-back season as a part-time player in 2002. On September 16, 2002, the Dodgers had a crucial game against the San Francisco Giants. In the top of the 9th inning, he robbed Rich Aurilia of a potential game-tying home run to protect the 7–6 victory. The Giants went on to make the playoffs and the Dodgers did not. As a free agent he subsequently attracted the attention of the San Francisco Giants, who had just been defeated in the World Series. San Francisco signed Grissom, and he enjoyed two more productive seasons as their starting center fielder. The Giants were successful as well, winning the NL West in 2003 and missing the wild card by one game in 2004. Marquis won the 2003 Willie Mac Award for his spirit and leadership. Grissom's production dipped again in 2005, and in a season of struggles by the Giants, he was released. On January 3, 2006, the Chicago Cubs signed him to a minor league contract and invited him to spring training as a non-roster player.