To describe the occurrence of vaccine-associated paralytic poliomyelitis (VAPP) in Brazil between 1995 and 2001 and to determine the level of risk for this adverse event. This retrospective study utilized data from acute flaccid paralysis investigation and notification records from the Ministry of Health in Brazil. Cases were defined as individuals with a diagnosis of acute flaccid paralysis and a positive stool culture or sequelae compatible with poliomyelitis appearing up to 60 days after the beginning of motor impairment. Also included were individuals in any age range who had contact with vaccinated persons between the 4th and 40th day before the onset of the disease and who developed motor impairment between 4 and 85 days after this contact. Risk was calculated as the ratio between the number of cases and the respective number of doses given in a year, according to the National Immunization Program. Ten cases of VAPP were recorded in the period. The mean age of the cases was 4.7 months. Four cases were associated with the first dose, four with the second dose, and two cases were attributed to contact. In two cases type 1 virus was identified; in one case, type 2; and in three cases, type 3. More than one serotype was isolated in four cases. In all 10 cases the serotype was determined. The observed risk for VAPP during the period studied was 1:5.11 million when considering only the first dose and 1:10.67 million for all the doses. The main technical and ethical dilemma of the post-poliomyelitis elimination stage is the occurrence of paralytic cases that result from the vaccine policy itself, whose objective is the eradication of polio.