Голосование по выбору игроков в стартовые пятерки обеих команд началось 13 ноября и завершилось 18 января. На этот раз болельщики получили возможность высказать свое мнения несколькими возможными способами, а в Интернете голосование велось на 17 языках. По итогам этого опроса российский легионер "Юты" не попал в состав. Однако помимо стартовой пятерки, игроков которой выбирают болельщики, каждая команда заявляет семерых запасных: двух защитников, двух форвардов, центрового и еще двоих баскетболистов по выбору вне зависимости от амплуа. Их имена определяются в голосовании тренеров 29 команд НБА. Каждый из них имеет право отдать голос любому игроку, но только не тому, кто играет в его команде.
Именно по результатам опроса специалистов Кириленко получил место в составе команды Западной конференции.
Помимо россиянина Кириленко и Тима Данкана, который родился на Виргинских островах, в составы обеих команд вошли еще 4 игрока не из США: это китайский центровой Яо Мин из "Хьюстона", немец Дирк Новицки из "Далласа", серб Пея Стоякович из "Сакраменто" и канадец Джамаль Маглуар из "Нового Орлеана". Из этой шестерки только последний будет играть за команду Востока. По числу иностранцев Матч всех звезд 2004 года станет повторений прошлогоднего, в котором был установлен рекорд НБА.