Вопрос не такой простой как кажется. Все зависит от того, что считать "мобильным телефоном" и что считать "игрой".
Если брать широкое определение - первые мобильные устройства с чем то игровым появились еще в начале 1990-х. Пейджеры и ранние трубки иногда имели простейшие встроенные развлечения типа теста реакции или генератора случайных чисел.
Если брать конкретную игру с геймплеем - да, это Tetris на Hagenuk MT-2000, 1994 год. Немецкая компания, телефон почти никто не помнит.
Если брать первую игру которую увидел массовый потребитель - Nokia Snake 1997. Благодаря масштабу распространения Nokia 6110 именно Змейка стала культурным феноменом и первой "мобильной игрой" в массовом сознании.
Если брать первую загружаемую игру (не встроенную) - это уже эпоха WAP и Java ME, примерно 1999-2001 годы.
Так что правильный ответ зависит от угла зрения.