В 1996 году Грейнинг в сотрудничестве с Дэвидом Коэном приступил к созданию научно-фантастического мультсериала. Коэн был единомышленником Грейнинга, тоже увлекался научной фантастикой, и особенно полюбил ее после просмотра сериала «Звездный путь». К тому же Коэн очень ценил творчество таких выдающихся писателей-фантастов, как Артур Кларк и Станислав Лем. Именно серьезное отношение к научной фантастике стало для Коэна отправной точкой нового сериала: «Мы с Мэттом Грейнингом с самого начала решили не делать сериал слишком глупым. У нас совсем не было желания высмеивать научную фантастику, разве что сделать ее забавной».

Кроме того, Коэн обладал всеми необходимыми знаниями для решения неизбежных технологических проблем, возникающих в процессе научно-фантастических приключений, например – как преодолевать межгалактические расстояния за разумное время. Это вечная проблема в научной фантастике, поскольку ни космические корабли, ни что-либо другое не могут передвигаться быстрее скорости света, а свету понадобится два миллиона лет, чтобы долететь до ближайшей спиральной галактики. Коэн предложил два решения, которые позволили бы персонажам нового мультсериала перемещаться между галактиками за разумное время. Одно сводилось к включению в сюжет информации о том, что в 2208 году ученым удалось превысить скорость света, а другое, еще более смелое, заключалось в использовании в новом сериале двигателя, который способен достигать сверхсветовых скоростей, ускоряя Вселенную вокруг него, а не корабля, на котором он установлен.

Грейнинг и Коэн начали работать над сюжетом, основанном на приключениях персонажа по имени Филипп Дж. Фрай, нью-йоркского разносчика пиццы, который был заморожен в криогенной камере в первые часы 2000 года. Проснувшись через тысячу лет в Новом Нью-Йорке, Фрай с нетерпением ждет начала новой жизни в XXXI веке, надеясь на то, что его нынешняя карьера будет более достойной, чем прежняя. Но как это ни печально, он с досадой узнает, что ему должны вживить специальный карьерный чип, обрекающий на ту же работу – разносчика пиццы. Единственное отличие состоит в том, что вместо доставки пиццы в Нью-Йорке он будет развозить ее по разным планетам, работающим в компании «Межпланетный экспресс».

Определившись с Фраем, Грейнинг и Коэн приступили к созданию других персонажей команды «Межпланетного экспресса». В частности, коллегами Фрая стали: Лила – одноглазая девушка-мутант, неоднократно разбивавшая сердце Фрая; Бендер – робот с порочными хобби, такими как воровство, азартные игры, мошенничество, выпивка и еще кое-что похуже; профессор Хьюберт Дж. Фарнсворт –160-летний основатель компании «Межпланетный экспресс»; доктор Джон Зойдберг – омароподобный врач компании «Межпланетный экспресс»; Гермес Конрад – бывший олимпийский чемпион по лимбо и бухгалтер компании; а также Эми Вонг – стажер.

Во многих отношениях «Футурама» должна была напоминать любой классический комедийный сериал, в котором действие происходит на работе, наподобие американского сериала «Такси» или британского – «Компьютерщики» (The IT Crowd). Единственное отличие состояло в том, что в новом фантастическом мультсериале была возможна любая сюжетная линия, поскольку экипаж «Межпланетного экспресса», доставляющий посылки по всей Вселенной, мог встречаться с разными инопланетянами на удивительных планетах со своими специфическими проблемами.