В 1983 году старший брат, Дэн Кейс, представил Стива руководству компании Control Video Corporation (CVC). CVC занималась поставками компьютерных видеоигр для персональных компьютеров Атари (Atari). Эти игры можно было запускать в режиме on-line, подключившись к игровому компьютеру компании с помощью модема (в то время мало кто имел у себя дома ПК). Стиву Кейсу сразу же предложили работать консультантом по маркетингу. Кейс первоначально был внештатным консультантом, работая на полставки. Он занимался поисками инвестором для открытия и разработки новых направлений компании.
Здесь Кейсу пригодился его опыт менеджера, а в дальней перспективе, пригодилось и его образование политика. Именно здесь Стив Кейс получил настоящий опыт работы в своей следующей сфере деятельности В CVC Кейс познакомился с Джимом Кимси (Jim Kimsey), который был промышленным консультантом фирмы. В это время начался временный спад популярности компьютерных игр. Наступил кризис старого направления деятельности фирмы и CVC почти обанкротилась. В 1985 году Кимси, Кейс и ведущие сотрудники старой фирмы основали новую компанию Quantum Computer Services.
Кимси стал руководителем, назначив Кейса вице-президентом по маркетингу, а в 1987 сделал его своим заместителем. Когда же Кимси ушел в отставку с главного руководящего поста фирмы, он продвинул Кейса на свое место. В 1991 году Кейс стал исполнительным директором, а в 1995 году – президентом.
Важным моментом для компании Quantum Computer Services было заключение Кейсом соглашения о партнерстве с производителями ПК, после чего компания стала процветать, контракты начали приносить прибыль. В 1985 году Кейс заключил с Commodore Business Machines, производителей ПК Commodore 64, соглашение об использовании персональными компьютерами Commodore 64 сервиса Quantum Link (Q-Link) для передачи информации в сети. В 1988 Стив Кейс заключил аналогичную сделку с Apple Computer – этот сервис назывался AppleLink. А для IBM появилась PC–Link. PC–Link предлагал новостные и справочные услуги. В 1989 году, компания Кейса объединила эти сервисы, чтобы пользователи компьютеров разных фирм могли общаться между собой. Объединенные сервисы назвали America Online (AOL). Quantum Computer Services теперь занимались электронной почтой, чатом, обменом файлами, играми и т. д.