In 1988, Martin teamed up with Billy Sheehan, Pat Torpey, and Paul Gilbert to form Los Angeles supergroup Mr. Big. The band combined "shredding" musicianship with melodic vocal harmonies. The reputations of the players generated immediate interest in fellow musicians, and the band was signed to Atlantic Records in 1989. That year, the band released their eponymous debut, which received critical and commercial success in the US and Japan. In June 1990, the group toured America with the Canadian band Rush.