And Then Nothing Turned Itself Inside-Out foi gravado no estudio Alex the Great en Nashville, Tennessee, e foi mesturado en The Big House en Manhattan, Nova York. O álbum foi producido por Roger Moutenot e lanzado o 22 de febreiro de 2000 por Matador Records. O título do disco deriva probablemente dunha cita de Sun Ra: "...At first there was nothing...then nothing turned itself inside-out and became something" (ao principio non había nada... e despois a nada volveuse do revés e converteuse nalgo). A arte do álbum está realizada con fotografías do fotógrafo surrealista e profesor de Yale Gregory Crewdson.
O álbum chegou ao número 138 da lista Billboard 200 nos Estados Unidos, sendo o seu primeiro traballo en entrar nesta lista.[1] En xaneiro de 2003 o disco levaba vendidas 114 000 copias nos Estados Unidos segundo Nielsen SoundScan.[2]
