Cullin was born in Santa Fe, New Mexico, of Scotch-Irish and Cherokee descent.
The New York Times has described Cullin's writing as "brilliant and beautiful," but the author has confessed that "half the time I'm not even sure why I make choices in writing, or how it works when it works."
Cullin's novel Tideland was adapted for the screen and directed by Terry Gilliam in 2003, and the author also made a brief cameo appearance in the film, later stating about his time on the set: "There was a part of me that wanted to watch and experience every aspect of what Terry was doing… and he allowed me to do that while I was there if I wished to… but at the same time, I didn’t want his process to become too demystified… because I wanted to buy a ticket someday and sit down in a dark theater and simply watch the film without knowing too much about how it was filmed." Despite mixed reviews from critics, Gilliam's film adaptation won the 2005 FIPRESCI prize at San Sebastián International Film Festival.
In 2005, Cullin published his sixth novel, A Slight Trick of the Mind, a portrait of Sherlock Holmes in old age, for which The New York Times praised the author as being "an unusually sophisticated theorist of human nature," and Carolyn See of The Washington Post stated that "you don't read it to be 'improved' but for the plain joy of seeing what the language can do in the hands of an affectionate, very accomplished writer." The audiobook edition of the novel won the Audio Publishers Association's 2006 Audie Awards for Unabridged Fiction.
Cullin's seventh novel The Post-War Dream was published by Random House in March 2008.
In April 2012, and to coincide with celebration of National Poetry Month, Cullin published The House of Special Purpose, a long narrative poem written almost two decades previously and featuring illustrations by Peter I. Chang, which chronicles the last days of the Romanov family during the Russian Revolution of 1918.
From May 2012 to February 2013, Cullin serialized the novel Everything Beautiful is Far Away as an online monthly magazine through the Issuu publication site. The book was written in collaboration with Peter I. Chang, and featured monthly guest artists and musicians, including Moby, Tsutomu Nakayama, Fights Monsters, Pleq, IP (Identity Problem), Caitlin Kirkley, DJ Terrapin, Chemical Tapes, Wind In Willows, Incompetech, Adriana Pasley, and The Ghost of Mendelsshon. Each monthly issue of Everything Beautiful is Far Away is free to read online via the Issuu site: http://issuu.com/lo-vi/docs.
A film version of Cullin's A Slight Trick of the Mind, titled Mr. Holmes, with Ian McKellen starring as Sherlock Holmes, written by Jeffrey Hatcher and directed by Bill Condon, was released in 2015.
While attending the University of Houston in the mid 1990s, Cullin befriended the author Mary Gaitskill. Gaitskill taught him in several writing classes. She remained a mentor after he dropped out of college and moved to Tucson, Arizona to write. Since then, Cullin and Gaitskill have stayed friends, and in 2005 they did a one-on-one author appearance at Manhattan's Housing Works.
Some of Cullin's early unpublished writings (including Afternoon Misdemeanors, The House of Special Purpose, and 6 Poems) are housed at Syracuse University in its archive collection of poet scholar Robert S. Phillips' papers, letters, manuscripts, and correspondence.
Along with writers including Salman Rushdie and Amy Tan, Cullin is a founding author of the non-profit Red Room website.
Cullin has worked with Giant Sand's Howe Gelb, helping to design the cover and logo for Gelb's 2003 solo album The Listener.
The following year, with Canadian musicians Todd Bryanton and Rob Bryanton, he co-wrote the song "Lift Me Up To Sweet Jesus" for the soundtrack of Terry Gilliam's Tideland, a film based on his novel of the same name, and in which he has a cameo appearance.
Cullin is credited as the producer of Peter I. Chang's film I Want to Destroy America, a documentary about the life of Hisao Shinagawa., and he is also credited as the cinematographer and producer on Peter I. Chang's 2008 documentary Tokyo is Dreaming.Tideland (2005) – as passenger on bus; Terry Gilliam's film version of Mitch Cullin's novel
Getting Gilliam (2006) – as himself; Vincenzo Natali's documentary about Terry Gilliam and the making of Tideland
This Band Has No Members (2006) – as himself; unreleased concert film of Howe Gelb performing in Kyoto, Japan
I Want to Destroy America (2006) – producer/interviewer; Peter I. Chang's documentary about Hisao Shinagawa
Making of Tideland (2007) – as himself; featurette on US, Canadian, and UK DVD editions of Terry Gilliam's Tideland
Regina Monologue (2007) – as himself; short film released only as an Easter egg on Disc 2 of the UK DVD edition of Terry Gilliam's Tideland
Q&A with Terry Gilliam and Mitch Cullin at the Hay Festival (2007) – as himself; bonus feature on the UK DVD edition of Terry Gilliam's Tideland
Tokyo is Dreaming (2008) – producer/cinematographer; Peter I. Chang's documentary about modern-day Tokyo
Mr. Holmes (2015) – an adaptation of Cullin's novel A Slight Trick of the Mind