Премия «Небьюла» была учреждена в 1965 году организацией фантастов США (Science Fiction and Fantasy Writers of America). Присуждается раз в год голосованием членов SFWA. Первое вручение состоялось в 1966 году.
Идею учреждения премии предложил секретарь-казначей SFWA Ллойд Биггл — младший в 1965 году, а Джуди Блиш разработал дизайн награды: прямоугольный блок прозрачного пластика, внутри которого находятся кварцевый кристалл и серебристая спиральная туманность. Оттуда, собственно, и пошло название премии — «звездная туманность».
В отличие от премии «Хьюго», эта награда присуждается на основе голосования только членов SFWA, а не всех желающих. «Небьюла» изначально вручалась в четырех номинаций: «Роман», «Новелла», «Новлетта» и «Рассказ». Они присуждаются каждый год и по сей день. Единственное, в 2018-м была добавлена номинация за лучшее написание видео- или настольной игры. Премия нумеруется по году выхода произведения.
Номинированные работы определяются каждый год с 15 ноября по 15 февраля путем публикации авторами — членами организации. Чтобы стать соискателем, произведение должно быть выдвинуто не менее чем 10 членами SFWA.
Шесть работ, которые получают наибольшее количество номинаций, составляют итоговый бюллетень. Также существует возможность добавлять дополнительных кандидатов по решению членов SFWA. Затем представители организации голосуют за бюллетень в течение всего марта, а окончательные результаты представляются на церемонии награждения в мае. Авторам не разрешается номинировать собственные работы.
Вместе с «Небьюлой» на церемонии награждения вручаются несколько других наград. Премия Рэя Брэдбери — за выдающуюся драматическую презентацию. Премия Андре Нортона — за выдающуюся научную фантастику для взрослых. «Солнцестояние» — за общий вклад в фантастику. «Грандмастер» — за особые прижизненные заслуги в области научной фантастики.
Премия «Небьюла» считается «научно-фантастическим эквивалентом» «Эмми». А наличие у автора даже просто номинации на нее существенно повышает интерес к нему у читающей публики.