Oh, I found this on 3D Realms homepage regarding Remedy's first game Death Rally: "Originally released September 6, 1996."
UPDATED:
Remedy say on there homepage founded in 1995 and this is taking from there homepage regarding the history of Max Payne and 3DMark:
"In late 1996, after Death Rally was finished, people at Remedy started brainstorming ideas about a "3rd person action game". A prototype and design document of the game were created and shown to 3D Realms, who immediately fell in love with the idea. A development contract was signed and work on Max Payne began.
In 1997, Remedy created Final Reality™, a 3D accelerator benchmark program, for VNU Business Publications. It quickly became a widely used standard in 3D accelerator benchmarking with over 5 million copies distributed worldwide.
While Final Reality™ was an unbelievable success, it did not fit into Remedy's focus of creating action-packed games. A new company was founded in November 1997. Futuremark was born. Today Futuremark has established 3DMark as the defacto standard in 3D benchmarking. Over 20 million copies of subsequent 3DMarks have been distributed."