AMANDA is a high-energy neutrino telescope presently under construction at the geographical South Pole. In the Antarctic summer 1995/96, an array of 80 optical modules (OMs) arranged on 4 strings (AMANDA-B4) was deployed at depths between 1.5 and 2 km. In this paper we describe the design and performance of the AMANDA-B4 prototype, based on data collected between February and November 1996. Monte Carlo simulations of the detector response to down-going atmospheric muon tracks show that the global behavior of the detector is understood. We describe the data analysis method and present first results on atmospheric muon reconstruction and separation of neutrino candidates. The AMANDA array was upgraded with 216 OMs on 6 new strings in 1996/97 (AMANDA-B10), and 122 additional OMs on 3 strings in 1997/98.