Pražskou společnost, známou později jako Phoenix Arts, založili po návratu z vojny v roce 1993 Denis Černý a Jindra Tichota. Zpočátku to byla spíše jen počítačová firma, tedy sestava a prodej PC a software na zakázku. Vydělané peníze pak investovali na dokoupení dalších věcí na muziku a animace. Phoenix Arts oficiálně vzniká na přelomu ledna a února 1994.
Na jaře roku 1994 se pustili do výroby jejich úplně první hry. Měla to být multimediální obdoba klasické hry „Šibenice“. V té době se také poznali s Radkem Ševčíkem, který se taky rozhodl pro programování. Celou věc s Paranoiou vlastně začal on, něco se mu nelíbilo na Dune II a tak začal tvořit něco podobného. Poté, když už byl s vývojem dál, než oni s multimediální šibenicí, vykašlali se na ni a pustili se naplno do vývoje Paranoie. Po čase přibrali do týmu ještě Petra Havlíčka (grafika) a Vendelína Tůmu (hudba). Hra šla nakonec do prodeje na podzim roku 1995.
Po úspěchu prvního dílu začali pracovat na pokračování Paranoia II, které vyšlo v roce 1996. Posledním titulem byla opět strategie, vydaná v roce 1998 pod názvem Husita. Tím de facto končí historie Phoenix Arts jako samostatného vývojáře a distributora, neboť tým se stal součástí nově vzniklého Illusion Softworks (Denis Černý je hlavním programátorem enginu LS3D).