In 1988 Stewart began playing with one of the most famous bass players of all time, Stanley Clarke, and the two of them realized that something interesting might result from their collaboration. Stewart had been working with singer-songwriter Deborah Holland on a soundtrack. She let him listen to a few songs that she had written, and Stewart liked them so much that he asked her to record them with him and Stanley Clarke. Stewart and Stanley played, arranged, and produced the songs, and together with Deborah, they released the finished album under the name of Animal Logic.

The tour that followed the release of their eponymous debut album (Animal Logic, 1989) put Stewart back on stage, playing drums in front of large, enthusiastic crowds. Fans of both the Police and Stanley Clarke saw the project as a rare chance to witness two "monsters" of rhythm perform together. Although the success of these initial efforts prompted Animal Logic to record a second album together (Animal Logic II, 1991), no supporting concert tour followed. There would be no other Animal Logic releases in the future.