Fuller began his career as a dancer/actor, appearing on Broadway in Carousel, The Music Man, Kean, Bravo Giovanni, and Funny Girl. When Barbra Streisand headed to London for the West End production of the latter, Fuller was tapped to choreograph it, then repeated the task for the American tour. Additional touring productions Fuller has directed and choreographed include I Do! I Do!, Kismet, and On a Clear Day You Can See Forever.
In Europe, Fuller has directed and choreographed productions of West Side Story in Vienna and Nuremberg, created Jazz and the Dancing Americans for the Opera House Ballet in Graz, and directed the European premieres of Leonard Bernstein's Candide and On the Town and George Gershwin's Girl Crazy. He also directed and choreographed the mid-1980s hit Dave Clark European tour of Jesus Christ Superstar (1992) multi-media musical Time in London. In 1997 he directed and choreographed JFK: A Musical Drama in Dublin, Ireland.
Fuller's Broadway credits as a choreographer include On the Twentieth Century, Merrily We Roll Along, and A Doll's Life. He has been nominated for the Drama Desk Award for Outstanding Choreography twice, for his work in Sweeney Todd and Evita, which also garnered him a Tony nod. He choreographed the original West End production of the latter and directed and choreographed the 2004 US national tour as well.
Fuller was involved in a relationship with fellow choreographer/director Michael Bennett for many years. The 1996 documentary On Your Toes . . . The Making Of - Choreographer Larry Fuller documents the making of the musical production "On Your Toes" with the Stuttgart Ballet Company in 1990.