Although the Appropriateness Evaluation Protocol (AEP) has been widely used during the past decade, several methodological concerns have not yet been properly resolved, including the possible influence of low completeness of the medical records on the results yielded by the AEP in retrospective studies. We examined medical records for a random sample of 345 patient-days with the AEP, according to a protocol that included several variables potentially related to inappropriateness. The completeness of physician and nursing notes was also assessed. The proportion of inappropriate days of hospitalization was 36.2%. In the crude analysis, significantly higher proportions of inappropriateness were found for lower values of completeness. Factors related to the inappropriateness of stay were summer season, elective admission, no previous admissions, surgical and medical-surgical service in charge, and the day sampled falling within the last third of the hospital stay. Adjustment for the completeness level of medical records did not substantially change the strength of the association between these factors and the inappropriateness of hospital stay. Completeness level itself did not show any significant association with the proportion of inappropriate days in the adjusted analysis.